Velocizza l'algoritmo di ranking
In un vecchio torneo, i tecnici del software avevano implementato un algoritmo di ranking basato su bubble sort. Allora il numero di partecipanti era ridotto e quell’approccio funzionava senza problemi. Ma oggi i partecipanti sono diventati troppi, e ti viene richiesto di rendere più rapido l’algoritmo di ranking.
Ogni squadra ha un numero identificativo (unico) e un punteggio. Le squadre devono essere ordinate in ordine decrescente rispetto al punteggio (prima i punteggi più alti, poi quelli più bassi), e quelle con lo stesso punteggio devono mantenere l’ordine in cui compaiono nell’input. Perciò ti viene chiesto di implementare un ordinamento stabile.
Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ ).Le successive
n righe contengono coppie di valori separate da uno spazio (), che rappresentano l’identificatore unico di ogni squadra e il punteggio ottenuto.Output
Il programma deve stampare
n righe. Ogni riga conterrà due interi: l’id della squadra e il punteggio corrispondente.Esempi
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