Problem : 264 - Archery

Problem Statistics

Solved Member: 2　　Submission: 42　　User Tried: 2

Statement:

一場箭術比賽規則如下所示。在一條直線上排著N個靶子，靶子從左到右序號依次為從1到N。同時有2N個選手，在比賽的任何時刻，同一個靶位上都有兩個選手。比賽的每一輪按照如下規則進行：

在同一個靶位的兩位選手比賽一場決出勝者，然後所有選手按照如下規則移動：

　•在2到N號靶位上的勝者移動到他們的左側的靶位（即分別移動到1到N-1號靶位）

　•在2到N號靶位上的負者，以及1號靶位上的勝者，停留在同一個靶位。

　•1號靶位上的負者移動到N號靶位。

這場比賽持續R輪（R>=2N）。

你作為唯一一個準時到達的選手（其他選手已經提前到達了並且排成了一行），你現在要做的就是插入這個隊伍，在你進入隊伍後，隊列中前兩個選手將對應一號靶位，接下來兩個將對應二號靶位，以此類推。

所有的選手（包括你）都用一個數值衡量技術水平，在同一個靶位上，數值比較小的選手會成為勝者，沒有兩個選手的技術水平相同。

在了解了所有選手的技術水平之後，你需要找到一個位置插入使得你最終對應的靶位序號盡量小，在此前提下，你希望你初始時對應的靶位序號盡量大。

Input:Output:

第一行包含整數N和R，1<=N<=200000，2*N<=R<=1000000000。

接下來2*N行給出了選手的等級。第一行是你的等級，其餘各行是其他選手的等級。每個選手一行，按照他們已經排好的順序（從左到右）。這2*N行每行包含一個1~2*N的整數，1表示最好，2*N表示最差。沒有兩個選手的等級相同。

一個1~N的整數，表示你在開始比賽時所在的靶位。

Sample Input:Sample Output:

Sample #1:
4 8
7
4
2
6
5
8
1
3

Sample #2:
4 9
2
1
5
8
3
4
7
6

Sample #1:
3

Sample #2:
2

HINT:

Sample 1:
你是排名倒數第二的弓箭手。如果你從靶1開始比賽，接下來你將移到靶4而且一直留在靶4直到最後。如果你從靶2或靶4開始，你將會留在那裡直到最後。如果你從靶3開始，你將會擊敗最差的選手，然後移到靶2並留在那裡。

Sample 2:
你是排名第二的弓箭手。最厲害的選手已經在靶1並且在整個比賽期間將會一直留在那裡。因此不管你從哪個箭靶開始，你總會不斷地從靶4依序經過所有箭靶，為了讓你在9回合的對戰後停在靶1，你必須從靶2開始整個比賽。

Source:

IOI 2009

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	65536kb
0-2	1000ms	65536kb
1	2000ms	65536kb	1
2	2000ms	65536kb	1
3	2000ms	65536kb	1
4	2000ms	65536kb	1
5	2000ms	65536kb	1
6	2000ms	65536kb	1
7	2000ms	65536kb	2
8	2000ms	65536kb	2
9	2000ms	65536kb	2
10	2000ms	65536kb	2
11	2000ms	65536kb	2
12	2000ms	65536kb	2
13	2000ms	65536kb	2
14	2000ms	65536kb	2
15	2000ms	65536kb	2
16	2000ms	65536kb	2
17	2000ms	65536kb	2
18	2000ms	65536kb	2
19	2000ms	65536kb	2
20	2000ms	65536kb	2
21	2000ms	65536kb	2
22	2000ms	65536kb	2
23	2000ms	65536kb	2
24	2000ms	65536kb	2
25	2000ms	65536kb	2
26	2000ms	65536kb	2
27	2000ms	65536kb	2
28	2000ms	65536kb	2
29	2000ms	65536kb	2
30	2000ms	65536kb	2
31	2000ms	65536kb	2
32	2000ms	65536kb	2
33	2000ms	65536kb	2
34	2000ms	65536kb	2
35	2000ms	65536kb	2
36	2000ms	65536kb	2
37	2000ms	65536kb	2
38	2000ms	65536kb	2
39	2000ms	65536kb	2
40	2000ms	65536kb	2
41	2000ms	65536kb	2
42	2000ms	65536kb	2
43	2000ms	65536kb	2
44	2000ms	65536kb	2
45	2000ms	65536kb	2
46	2000ms	65536kb	2
47	2000ms	65536kb	2
48	2000ms	65536kb	2
49	2000ms	65536kb	2
50	2000ms	65536kb	2
51	2000ms	65536kb	2
52	2000ms	65536kb	2
53	2000ms	65536kb	2