Acelere o algoritmo de classificação
Num torneio antigo, os engenheiros de software implementaram um algoritmo de classificação baseado em bubble sort. Naquela altura, o evento não tinha muitos participantes, por isso funcionava razoavelmente bem. Mas agora, com o número de participantes muito maior, pedem-te para acelerar este algoritmo.
Cada equipa tem um número único (um identificador) e uma pontuação. As equipas devem ser ordenadas por pontuação de forma decrescente (primeiro as pontuações mais altas, depois as mais baixas) e, caso tenham a mesma pontuação, devem permanecer na mesma ordem em que aparecem no input. Ou seja, precisas de implementar uma ordenação estável (stable sort).
Entrada
A primeira linha do input contém um único inteiro
n (1 ≤ n ≤ ).As próximas
n linhas contêm pares separados por espaço (), que representam o identificador único de cada equipa e a pontuação que ela obteve.Saída
O programa deve imprimir
n linhas. Em cada linha, devem aparecer dois inteiros: o id da equipa e a pontuação correspondente.Exemplos
Entrada | Saída |
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