/
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は、プログラミングコンテストの順位表を作成する担当者です。
このコンテストには N 人の参加者がおり、各参加者には 1 から N までの番号が付けられています。参加者 i のレーティングは A_i です。
コンテストでは、各参加者がスコアを獲得しました。参加者 i の獲得スコアは B_i です。コンテストの得点方式の性質上、獲得スコアは必ず自分のレーティング以上となります。すなわち、すべての i (1 \leq i \leq N) について B_i \geq A_i が成り立ちます。
順位表は以下のルールで作成されます。2人の参加者を比較するとき、以下の基準を優先度の高い順に適用し、上位(順位の数字が小さい方)を決定します:
- 獲得スコアが高い参加者を上位とする。
- 獲得スコアが同じ場合は、レーティングが高い参加者を上位とする。
- 獲得スコアもレーティングも同じ場合は、参加者番号が小さい参加者を上位とする。
参加者番号はすべて異なるため、上記のルールによりすべての参加者の順位は一意に定まります。
高橋君の代わりに、各参加者の番号を順位が高い方から順に出力するプログラムを作成してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- A_i \leq B_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N A_1 B_1 A_2 B_2 \vdots A_N B_N
1 行目には、参加者の人数を表す整数 N が与えられる。続く N 行のうち i 行目には、参加者 i のレーティング A_i と獲得スコア B_i が、スペース区切りで与えられる。
出力
N 行にわたって、順位が高い方から順に参加者の番号を出力せよ。i 行目には、i 位の参加者の番号を出力せよ。
入力例 1
3 100 200 150 200 120 300
出力例 1
3 2 1
入力例 2
5 1000 1500 800 1500 1200 1500 500 2000 900 1000
出力例 2
4 3 1 2 5
入力例 3
10 50 300 200 300 200 250 100 400 150 300 300 300 80 200 400 400 150 150 250 300
出力例 3
8 4 6 10 2 5 1 3 7 9
Score : 300 pts
Problem Statement
Takahashi is in charge of creating the standings for a programming contest.
There are N participants in this contest, and each participant is assigned a number from 1 to N. The rating of participant i is A_i.
In the contest, each participant earned a score. The score earned by participant i is B_i. Due to the nature of the contest's scoring system, the earned score is always at least as large as one's own rating. That is, B_i \geq A_i holds for all i (1 \leq i \leq N).
The standings are created according to the following rules. When comparing two participants, the following criteria are applied in order of priority to determine who ranks higher (i.e., has a smaller rank number):
- The participant with a higher earned score ranks higher.
- If the earned scores are the same, the participant with a higher rating ranks higher.
- If both the earned score and the rating are the same, the participant with the smaller participant number ranks higher.
Since all participant numbers are distinct, the above rules uniquely determine the rank of every participant.
On behalf of Takahashi, write a program that outputs each participant's number in order from the highest-ranked to the lowest-ranked.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- A_i \leq B_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N A_1 B_1 A_2 B_2 \vdots A_N B_N
The first line contains an integer N representing the number of participants. In the following N lines, the i-th line contains the rating A_i and the earned score B_i of participant i, separated by a space.
Output
Over N lines, output the participant numbers in order from the highest-ranked to the lowest-ranked. On the i-th line, output the participant number of the participant ranked i-th.
Sample Input 1
3 100 200 150 200 120 300
Sample Output 1
3 2 1
Sample Input 2
5 1000 1500 800 1500 1200 1500 500 2000 900 1000
Sample Output 2
4 3 1 2 5
Sample Input 3
10 50 300 200 300 200 250 100 400 150 300 300 300 80 200 400 400 150 150 250 300
Sample Output 3
8 4 6 10 2 5 1 3 7 9