概要

各参加者を「スコアが高い順 → レーティングが高い順 → 番号が小さい順」という優先順位で並べ替え、上から順に参加者番号を出力する問題です。

考察

順位の決め方は「複数のキーでの並び替え（ソート）」そのものです。
つまり、各参加者 \(i\) を次の優先順位で比較すればよいです：

1. \(B_i\) が大きいほど上（降順）
2. \(B_i\) が同じなら \(A_i\) が大きいほど上（降順）
3. \(B_i, A_i\) も同じなら番号 \(i\) が小さいほど上（昇順）

ここで素朴に「順位表を1位から順に決める」ために、毎回「まだ選ばれていない中で最大の人」を全探索で探すと、\(N\) 回それを繰り返して \(O(N^2)\) になります。
\(N \le 2 \times 10^5\) なので、\(O(N^2)\) は間に合いません（TLEの原因）。

この問題は一括でソートすればよく、ソートは \(O(N \log N)\) で間に合います。

※ 制約にある \(B_i \ge A_i\) は入力の整合性を保証するだけで、順位付けの処理自体には特別な工夫は不要です。

アルゴリズム

1. 各参加者 \(i\) について、比較に使うキーを作って配列に入れる。
2. その配列をソートする。
3. ソート後の順に参加者番号を出力する。

Python の sort() は「昇順ソート」なので、降順にしたい項目（\(B_i\), \(A_i\)）は符号を反転させて (-B_i, -A_i, i) の形にします。

• 例：参加者が以下の3人だとする
  
  • 1: \((A,B)=(100,200)\) → キー \((-200,-100,1)\)
    
  • 2: \((A,B)=(150,200)\) → キー \((-200,-150,2)\)（同点200ならレート150が上）
    
  • 3: \((A,B)=(120,180)\) → キー \((-180,-120,3)\)
    これを昇順に並べると、2 → 1 → 3 の順になり、要求通りの順位になります。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（参加者情報の配列）

実装のポイント

• ソートキーを ( -B, -A, i ) として「昇順ソート＝順位の高い順」になるようにする。

• \(N\) が大きいので sys.stdin.readline を使って高速入力にする。

• 出力も "\n".join(...) でまとめて書くと高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    people = []
    for i in range(1, N + 1):
        a, b = map(int, input().split())
        people.append((-b, -a, i))
    people.sort()
    out = "\n".join(str(p[2]) for p in people)
    sys.stdout.write(out)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。