Задача №112333. Петя и Робот
Робот считает, что две тетради образуют беспорядок, если тетрадь с меньшим номером стоит правее тетради с большим номером. Например, в расстановке (2; 1; 5; 3; 4) беспорядки образуют три пары тетрадей (2; 1), (5; 3) и (5; 4), поэтому число беспорядков в такой расстановке равно 3.
После ремонта комнаты Петя забыл привычную расстановку своих тетрадей на полке и хочет её восстановить. Робот сохранил её, но он умеет сообщать только число беспорядков в сохраненной расстановке. Петя может попросить Робота поменять местами две тетради в сохраненной расстановке. После такого запроса Робот сохранит новую расстановку и сообщит число беспорядков в ней. Петя может повторять запросы до тех пор, пока не решит, что у него достаточно информации для восстановления привычной расстановки.
Требуется составить программу, которая, общаясь с Роботом, восстанавливает привычную расстановку тетрадей
Это интерактивная задача. В процессе тестирования ваша программа будет с использованием стандартных потоков ввода/вывода взаимодействовать с программой жюри, которая моделирует работу Робота.
Сначала ваша программа должна прочитать из стандартного потока ввода два целых числа \(n\) и \(m\) — количество тетрадей Пети и количество беспорядков в его привычной расстановке.
Затем протокол общения вашей программы и программы жюри следующий:
* Для перестановки двух тетрадей ваша программа выводит в стандартный поток вывода запрос в формате: swap \(i\) \(j\), где \(i\) и \(j\) — номера позиций тетрадей, которые Робот должен поменять местами (1 <= \(i\), \(j\) <= \(n\); i != j). После этого она должна считать из стандартного потока ввода одно целое число — количество беспорядков в получившейся расстановке. Ваша программа может сделать не более 300 000 запросов.
* Когда ваша программа сможет восстановить привычную расстановку тетрадей, она должна вывести эту расстановку в формате: answer \(p\), где \(p\) — последовательность из n различных целых чисел в диапазоне от 1 до \(n\), и завершить работу.
Запрос на обмен и вывод привычной расстановки должны завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) в Pascal/Delphi; fflush(stdout) или cout.flush() в С/C++.
Данная задача содержит четыре подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за первую подзадачу начисляются только в том случае, если все тесты из этой группы пройдены. Тесты второй, третьей и четвертой подзадач оцениваются по отдельности.
1 <= \(n\) <= 100. Подзадача оценивается в 30 баллов.
1 <= \(n\) <= 8000. Подзадача оценивается в 20 баллов.
1 <= \(n\) <= 60000. Подзадача оценивается в 30 баллов.
1 <= \(n\) <= 100000. Подзадача оценивается в 20 баллов.