Trier les grands produits
Étant donné
n paires de nombres (, ), (, ), …, (, ), il vous est demandé de les trier par ordre croissant si l’on définit la valeur d’une paire comme le nombre . Après ce tri, vous devez afficher les indices d’origine des paires. Si plusieurs solutions respectent cet ordre, vous devez alors privilégier celle dont les indices initiaux sont les plus petits.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ ).Les
n lignes suivantes contiennent chacune deux entiers (, ) (0 ≤ ≤ ) (1 ≤ ≤ ).Sortie
Le programme doit afficher les indices initiaux des paires après le tri.
Exemples
Entrée | Sortie |
5
0 3
0 4
0 1
0 2
0 5 | 3 4 1 2 5 |
6
1 1
0 2
1 2
2 1
0 1
2 3 | 5 1 2 3 4 6 |
Explications
- [1](0, 3) = 3 • [2](0, 4) = 4 • [3](0, 1) = 1 • [4](0, 2) = 2 • [5](0, 5) = 5
Après le tri → 1 2 3 4 5 ⇒ les indices initiaux sont :
[3] [4] [1] [2] [5].
- [1](1, 1) = 2 • [2](0, 2) = 2 • [3](1, 2) = 4 • [4](2, 1) = 4 • [5](0, 1) = 1 • [6](2, 3) = 12
Après le tri → 1 2 2 4 4 12 ⇒ les indices initiaux sont :
[5] [1] [2] [3] [4] [6].
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB