Acelera el algoritmo de clasificación
En un torneo antiguo, los ingenieros de software implementaron un algoritmo de clasificación basado en ordenamiento de burbuja (bubble sort). En aquel entonces, el torneo no tenía muchos participantes, así que ese método funcionaba bien. Pero ahora el número de participantes es demasiado grande. Te piden que hagas más veloz el algoritmo de clasificación.
Cada equipo tiene un número único (un identificador) y una puntuación. Los equipos deben ordenarse en orden descendente de sus puntuaciones (puntajes más altos primero y más bajos al final), y los equipos que tengan la misma puntuación deben mantener el orden en el que aparezcan en la entrada. Por lo tanto, debes implementar un ordenamiento estable (stable sort).
Input
La primera línea de la entrada contiene un solo entero
n (1 ≤ n ≤ ).Las siguientes
n líneas contienen pares separados por espacio () que representan el identificador único de un equipo y la puntuación que obtuvo.Output
El programa debe imprimir
n líneas. Cada línea debe contener dos enteros: el id del equipo y su puntuación.Examples
Entrada | Salida |
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