21517번 - Петя и Робот 다국어인터랙티브

문제

У Пети на полке стоят $n$ тетрадей с полным собранием его идей. Тетради пронумерованы различными целыми числами от 1 до $n$. У Пети есть привычная расстановка тетрадей (возможно, не в порядке нумерации), и он не любит, когда кто-то их переставляет. Петя купил специального Робота, который умеет запоминать расстановку тетрадей и вычислять число беспорядков в этой расстановке.

Робот считает, что две тетради образуют беспорядок, если тетрадь с меньшим номером стоит правее тетради с бóльшим номером. Например, в расстановке $(2, 1, 5, 3, 4)$ беспорядки образуют три пары тетрадей $(2, 1),ドル $(5, 3)$ и $(5, 4),ドル поэтому число беспорядков в такой расстановке равно 3.

После ремонта комнаты Петя забыл привычную расстановку своих тетрадей на полке и хочет её восстановить. Робот сохранил её, но он умеет сообщать только число беспорядков в сохраненной расстановке. Петя может попросить Робота поменять местами две тетради в сохраненной расстановке. После такого запроса Робот сохранит новую расстановку и сообщит число беспорядков в ней. Петя может повторять запросы до тех пор, пока не решит, что у него достаточно информации для восстановления привычной расстановки.

Требуется составить программу, которая, общаясь с Роботом, восстанавливает привычную расстановку тетрадей.

입력

출력

제한

• 1ドル \leqslant n \leqslant 100,000円$

인터랙션

Это интерактивная задача. В процессе тестирования ваша программа будет с использованием стандартных потоков ввода/вывода взаимодействовать с программой жюри, которая моделирует работу Робота.

Сначала ваша программа должна прочитать из стандартного потока ввода два целых числа $n$ и $m$ --- количество тетрадей Пети и количество беспорядков в его привычной расстановке.

Затем протокол общения вашей программы и программы жюри следующий:

• Для перестановки двух тетрадей ваша программа выводит в стандартный поток вывода запрос в формате: swap $i$ $j,ドル где $i$ и $j$ --- номера позиций тетрадей, которые Робот должен поменять местами (1ドル \leqslant i, j \leqslant n$; $i \neq j$). После этого она должна считать из стандартного потока ввода одно целое число --- количество беспорядков в получившейся расстановке. Ваша программа может сделать не более 300ドル,000円$ запросов.
• Когда ваша программа сможет восстановить привычную расстановку тетрадей, она должна вывести эту расстановку в формате: answer $p,ドル где $p$ --- последовательность из $n$ различных целых чисел в диапазоне от 1 до $n,ドル и завершить работу.

Запрос на обмен и вывод привычной расстановки должны завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) в Pascal/Delphi; fflush(stdout) или cout.flush() в С/C++.

힌트