Beschleunigung des Ranking-Algorithmus
Bei einem alten Turnier nutzten die Softwareentwickler zur Rangberechnung einen Algorithmus auf Basis von Bubble-Sort. Damals, als nur wenige Teilnehmende dabei waren, funktionierte das problemlos. Inzwischen ist die Zahl der Teilnehmenden jedoch stark gewachsen, und nun sollen Sie den Algorithmus beschleunigen.
Jedes Team verfügt über eine eindeutige Nummer (Identifier) sowie eine Punktzahl. Zur Sortierung sollen die Teams in absteigender Reihenfolge ihrer Punktzahlen angeordnet werden, also zuerst die Teams mit den höchsten Punkten und zuletzt diejenigen mit den niedrigsten Punkten. Für Teams mit gleicher Punktzahl muss die ursprüngliche Reihenfolge aus der Eingabe erhalten bleiben. Das bedeutet, Sie müssen eine stabile Sortierung implementieren.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ).Die folgenden
n Zeilen enthalten je zwei durch ein Leerzeichen getrennte Werte (): Hierbei steht für die eindeutige Kennung des Teams und für die erzielte Punktzahl.Ausgabe
Das Programm soll
n Zeilen ausgeben. In jeder Zeile stehen dabei zwei ganze Zahlen: die Kennung des jeweiligen Teams und seine Punktzahl.Beispiele
Eingabe | Ausgabe |
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