C. Сравнимые перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Для перестановки$$$^{\text{∗}}$$$ $$$g = (g_1, g_2, \ldots, g_m)$$$ определим функцию разворота $$$\operatorname{rev}(g) = (g_m, g_{m-1}, \ldots, g_1)$$$.

Существует скрытая перестановка $$$p$$$ длины $$$n$$$. Ваша задача — найти лексикографически наименьшую$$$^{\text{†}}$$$ перестановку $$$q$$$ длины $$$n$$$, такую что $$$q \gt p$$$ и $$$\operatorname{rev}(q) \gt \operatorname{rev}(p)$$$.

Однако вам не нужно выводить само $$$q$$$. Вместо этого вы должны вывести перестановку $$$r$$$ длины $$$n$$$, такую что $$$q_i = p_{r_i}$$$ для всех $$$1 \le i \le n$$$. Если такой $$$q$$$ не существует, сообщите об этом.

Чтобы найти ответ, вы можете задать не более $$$3n$$$ запросов вида $$$\texttt{? } i \; j$$$ ($$$1 \le i, j \le n$$$). Интерактор отвечает $$$1$$$, если $$$p_i \lt p_j$$$, и $$$0$$$ в противном случае. Интерактор не адаптивен, что означает, что перестановка $$$p$$$ фиксирована на протяжении всего взаимодействия.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$ Массив $$$x$$$ лексикографически меньше массива $$$y$$$ (то есть $$$x \lt y$$$), если и только если выполняется одно из следующих условий:

  • $$$x$$$ является префиксом $$$y$$$, но $$$x \ne y$$$; или
  • Пусть $$$i$$$ — первая позиция, где $$$x_i \neq y_i$$$ (если она существует), тогда $$$x_i \lt y_i$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^4$$$) — длина скрытой перестановки $$$p$$$.

Скрытая перестановка $$$p$$$ фиксирована для набора входных данных и не меняется в течение взаимодействия. Другими словами, интерактор не адаптивен.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^4$$$.

Протокол взаимодействия

Для каждого набора входных данных сначала считайте одно целое число $$$n$$$.

Вы можете задать до $$$3n$$$ запросов в каждом наборе входных данных.

Чтобы задать запрос, выведите строку в формате $$$\texttt{?} \; i \; j$$$ ($$$1 \le i, j \le n$$$).

В ответ на запрос вы получите:

  • $$$1$$$, если $$$p_i \lt p_j$$$;
  • $$$0$$$, если $$$p_i \ge p_j$$$;
  • $$$-1$$$, если вы сделали некорректный запрос или если превысили лимит в $$$3n$$$ запросов.

Если ваше решение сделает больше $$$3n$$$ запросов на одном наборе входных данных, или сделает некорректный запрос, ответ на запрос будет "-1". После такого ответа ваше решение должно немедленно завершиться, чтобы получить вердикт Неправильный ответ. В ином случае вердикт может получиться любым.

Когда вы определите ответ для текущего набора входных данных, выведите одно из следующих:

  • Если не существует допустимой перестановки $$$q$$$, выведите $$$\texttt{!} \; -1$$$.
  • В противном случае выведите $$$\texttt{!} \; r_1 \; r_2 \; \ldots \; r_n$$$, где $$$r$$$ — это перестановка длины $$$n$$$, и $$$q_i = p_{r_i}$$$.

Обратите внимание, что этот вывод не учитывается в лимите в $$$3n$$$ запросов.

После этого переходите к следующему набору входных данных или завершите программу, если больше нет наборов входных данных.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Обратите внимание, что интерактор не адаптивен, что означает, что скрытая перестановка не изменяется на протяжении всего взаимодействия.

Взломы

Чтобы совершить взлом, используйте следующий формат.

Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных должна содержать целое положительное число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^4$$$) — длину $$$p$$$.

Вторая строка каждого набора входных данных должна содержать $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

Вы должны гарантировать, что заданное $$$p$$$ является перестановкой, и что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^4$$$.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
3
5

1

4

1

0

1

0

9
Выходные данные


? 2 1

! 1 2 4 5 3

? 2 3

? 1 3

? 1 4

? 2 2

! -1

! 1 2 3 6 7 4 5 8 9
Примечание

В наборе входных данных взаимодействие происходит следующим образом.

РешениеЖюриОбъяснение
3Существует $$$3$$$ набора входных данных.
5В первом наборе входных данных скрытая перестановка $$$[5, 4, 2, 3, 1]$$$, длина $$$5$$$. Соответствующая перестановка $$$q = [5, 4, 3, 1, 2]$$$
? 2 11Решение спрашивает верно ли $$$p_2 \lt p_1$$$, и жюри отвечает $$$1$$$, так как $$$4 \lt 5$$$.
! 1 2 4 5 3Решение угадало ответ и вывело $$$r = [1, 2, 4, 5, 3]$$$, потому что, например, $$$q_3 = p_{r_3} = p_4 = 3$$$ и $$$q_2 = p_{r_2} = p_2 = 4$$$.
4Во втором наборе входных данных скрытая перестановка $$$[3, 1, 2, 4]$$$, длина $$$4$$$. Перестановка $$$q$$$ не существует для этого случая.
? 2 31Решение спрашивает, верно ли $$$p_2 \lt p_3$$$, и жюри отвечает $$$1$$$.
? 1 30Решение спрашивает, верно ли $$$p_1 \lt p_3$$$, и жюри отвечает $$$0$$$.
? 1 41Решение спрашивает, верно ли $$$p_1 \lt p_4$$$, и жюри отвечает $$$1$$$.
? 2 20Решение спрашивает, верно ли $$$p_2 \lt p_2$$$, и жюри отвечает $$$0$$$.
! -1Теперь решение знает, что $$$p = [3, 1, 2, 4]$$$ и определяет, что соответствующий $$$q$$$ не существует, поэтому выводит $$$-1$$$.
9В третьем наборе входных данных $$$p = [8, 1, 9, 3, 5, 4, 2, 6, 7]$$$, длина $$$n = 9$$$.
! 1 2 3 6 7 4 5 8 9Решение решает угадать ответ и выводит $$$r = [1, 2, 3, 6, 7, 4, 5, 8, 9]$$$, что оказывается правильным ответом.

Обратите внимание, что пустые строки в наборе входных данных ввода и вывода добавлены для ясности и не встречаются в реальном взаимодействии.