Ordenar os grandes produtos
Dadas
n duplas de números (, ), (, ), …, (, ), pretende-se ordená-las por ordem crescente considerando que o valor de cada dupla é o número . Pede-se que sejam impressos os índices iniciais dessas duplas após a ordenação. Se houver várias soluções possíveis, deve-se imprimir aquela em que os índices iniciais sejam menores.Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ).As próximas
n linhas contêm dois inteiros (, ) (0 ≤ ≤ ) (1 ≤ ≤ ).Saída
O programa deve imprimir os índices iniciais após a ordenação das duplas.
Exemplos
Entrada | Saída |
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 |
Explicação
- [1](0, 3) = 3 • [2](0, 4) = 4 • [3](0, 1) = 1 • [4](0, 2) = 2 • [5](0, 5) = 5
Depois de ordenar → 1 2 3 4 5 ⇒ os índices iniciais serão:
[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
Depois de ordenar → 1 2 2 4 4 12 ⇒ os índices iniciais serão:
[5] [1] [2] [3] [4] [6].
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB