ランキングアルゴリズムを高速化しよう
昔の大会では、ソフトウェアエンジニアたちがバブルソートを用いたランキングアルゴリズムを実装していました。当時は参加者数がそれほど多くなかったので、それでも十分に機能していたのです。しかし、現在では参加者数がとても多くなり、アルゴリズムを高速化することが求められています。
各チームには固有の番号（識別子）とスコアがあり、スコアが高い順（高いスコアを先に、低いスコアを後に）になるように並べ替えなければなりません。また、同じスコアのチームについては、入力で登場した順番が保たれるようにしなければなりません。つまり、安定ソートを実装する必要があります。
入力
最初の行には、単一の整数
n (1 ≤ n ≤ ) が与えられます。続く
n 行には、チームの固有の識別子とスコアを表す、スペース区切りのペア () が与えられます。出力
プログラムは
n 行を出力します。各行にはチームの id とスコアのペアを出力してください。例
入力 | 出力 |
6
1 10
4 20
5 7
2 20
8 10
9 15 | 4 20
2 20
9 15
1 10
8 10
5 7 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 10 MB