Сортировка больших произведений
Дано
n пар чисел (, ), (, ), …, (, ). Требуется отсортировать эти пары по возрастанию, считая значением каждой пары число . После сортировки необходимо вывести исходные индексы пар. Если существует несколько способов упорядочить пары, нужно выбрать тот, где среди равных значений пары с меньшими исходными индексами идут первыми.Входные данные
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ ).В следующих
n строках записаны по два целых числа (, ) (0 ≤ ≤ ) (1 ≤ ≤ ).Выходные данные
Программа должна вывести исходные индексы пар после сортировки.
Примеры
Входные данные | Выходные данные |
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 |
Пояснение
- [1](0, 3) = 3 • [2](0, 4) = 4 • [3](0, 1) = 1 • [4](0, 2) = 2 • [5](0, 5) = 5
После сортировки → 1 2 3 4 5 ⇒ исходные индексы:
[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
После сортировки → 1 2 2 4 4 12 ⇒ исходные индексы:
[5] [1] [2] [3] [4] [6].Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB