Accélérer l’algorithme de classement
Lors d’un ancien tournoi, les ingénieurs logiciels ont mis en place un algorithme de classement basé sur le tri à bulles. À l’époque, le tournoi ne comptait pas beaucoup de participants, donc cela suffisait. Mais aujourd’hui, le nombre de participants est bien plus élevé. On vous demande donc d’améliorer les performances de l’algorithme de classement.
Chaque équipe possède un numéro unique (un identifiant) ainsi qu’un score. Les équipes doivent être ordonnées par ordre décroissant de score (les meilleurs scores en premier, les moins bons en dernier), et les équipes ayant le même score doivent conserver l’ordre dans lequel elles apparaissent en entrée. Autrement dit, vous devez mettre en place un tri stable.
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ ).Les
n lignes suivantes contiennent des paires séparées par un espace (), représentant l’identifiant unique d’une équipe et le score obtenu par celle-ci.Sortie
Le programme doit afficher
n lignes. Chaque ligne doit contenir deux entiers : l’id de l’équipe et son score.Exemples
Input | Output |
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