Ускорение алгоритма ранжирования
На ранних этапах турнира инженеры-программисты использовали алгоритм ранжирования, основанный на пузырьковой сортировке. Когда участников было мало, это работало нормально. Но теперь команд стало слишком много, и вас просят ускорить алгоритм.
У каждой команды есть уникальный номер (идентификатор) и набранный ею результат (счёт). Необходимо упорядочить команды по убыванию результатов (сначала команды с наибольшими очками, в конце — с наименьшими). При этом команды, набравшие одинаковое количество очков, должны следовать в том же порядке, в каком они шли во входных данных. Значит, требуется стабильная сортировка.
Входные данные
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ ).Следующие
n строк содержат разделённые пробелом пары (), описывающие уникальный идентификатор команды и её результат.Выходные данные
Программа должна вывести
n строк. В каждой строке нужно указать два целых числа: id команды и её результат.Примеры
Входные данные | Выходные данные |
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