IOI '09 P1 - Archery

View as PDF

Submit solution


Points: 45 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

An archery tournament is held according to the following rules. There are N targets arranged in a line and numbered from 1 to N inclusive according to their place on the line (the leftmost target being target 1, and the rightmost target being target N). There are also 2N archers. At any time during the tournament, there are two archers on each target. Every round of the tournament goes according to the following procedure:

  • The two archers on each target compete with each other and determine a winner and a loser between them. Then all archers are rearranged as follows:
    • The winners on targets 2 to N inclusive move to the target on their left (i.e., targets 1 to N-1 respectively).
    • The losers on targets 2 to N inclusive, as well as the winner on target 1, remain on the same target.
    • The loser on target 1 moves to target N.

The tournament continues for R rounds, with the number of rounds being at least as many as the number of archers (i.e., R \ge 2N).

You are the only archer to arrive for the tournament exactly on time. All other 2N - 1 archers have arrived early and are already standing in a line. What you have to do now is to insert yourself somewhere into the line amongst them. You know that after you take your position, the two leftmost archers in the line will start the tournament on target 1, the next two will start on target 2 and so on, with the two rightmost archers starting on target N.

All the 2N archers in the tournament (including yourself) are ranked by skill, where a smaller rank corresponds to better skill. No two archers have the same rank. Also, whenever two archers compete, the one with the smaller rank will always win.

Knowing how skilled each of your competitors is, you want to insert yourself in such a way as to ensure that you will finish the tournament on a target with as small a number as possible. If there are multiple ways to do this, you prefer the one that starts at a target with as large a number as possible.

Write a program that, given the ranks of all archers, including yourself, as well as your competitors' arrangement on the line, determines on which target you should start the tournament, so that you can achieve your goals as defined above.

Constraints

1 \le N \le 200\,000 – The number of targets; also equal to half the number of archers

2N \le R \le 1\,000\,000\,000 – The number of tournament rounds

1 \le S_k \le 2N – The rank of archer k

Input Specification

Your program must read from standard input the following data:

The first line contains the integers N and R, separated by a space.

The next 2N lines list the ranks of the archers. The first of these lines contains your rank.

The rest of these lines contain the ranks of the other archers, one archer per line, in the order in which they have arranged themselves (from left to right).

Each of these 2N lines contains a single integer between 1 and 2N inclusive. A rank of 1 is the best and a rank of 2N is the worst. No two archers have the same rank.

Output Specification

Your program must write to standard output a single line containing a single integer between 1 and N inclusive: the number of the target on which you will start the tournament.

Grading

For a number of tests, worth a total of 60 points, N will not exceed 5\,000.

Also, for some of these tests, worth a total of 20 points, N will not exceed 200.

Sample Input 1

4 8
7
4
2
6
5
8
1
3

Sample Output 1

3

Explanation Of Sample 1

You are the second worst archer. If you start on target 1, you will then go to target 4 and stay there until the end. If you start on target 2 or 4, you will just stay there for the whole tournament. If you start on target 3, you will beat the worst archer and then move to target 2 and stay there.

Sample Input 2

4 9
2
1
5
8
3
4
7
6

Sample Output 2

2

Explanation Of Sample 2

You are the second best archer. The best one is already on target 1 and will stay there for the whole duration of the tournament. Thus, no matter where you start, you will always move from your target, going through all targets from 4 to 1 over and over again. In order for you to end on target 1 after 9 transitions, you have to start on target 2.


Comments

There are no comments at the moment.