Это интерактивная задача.
Есть загаданная перестановка \(p\) (нумерация начинается с \(1\)) из чисел от \(1\) до \(n\). Формально, для \(1 \leq i \leq n\), \(1 \leq p[i] \leq n\) и для \(1 \leq i < j \leq n\), \(p[i] \neq p[j]\). Известно, что \(p[1]<p[2]\).
За \(1\) запрос, вы даете \(3\) различные целые числа \(a,b,c\) (\(1 \leq a,b,c \leq n\)) и получаете медиану из \(\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}\).
В этом случае медиана — это \(2\)-й элемент (в \(1\)-индексации) последовательности, отсортированной в неубывающем порядке. Медиана чисел \(\{4,6,2\}\) равна \(4\), а медиана чисел \(\{0,123,33\}\) равна \(33\).
Можете ли вы найти загаданную перестановку за не более чем \(2n+420\) запросов?
Примечание: интерактор не является адаптивным: перестановка зафиксирована до того, как сделаны какие-либо запросы.
Протокол взаимодействия
Для каждого набора входных данных вы начинаете взаимодействие с чтения \(n\).
Чтобы выполнить запрос, выведите «? a b c», где \(a,b,c\) — \(3\) индекса, которые вы хотите использовать для запроса.
Числа должны удовлетворять требованиям \(1 \leq a,b,c \leq n\) и \(a \neq b\),\(b \neq c\),\(a \neq c\).
Для каждого запроса вы получите одно целое число \(x\): медиану из \(\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}\).
Если ваш запрос некорректен или вы задали более \(2n+420\) запросов, интерактор выведет «-1» и завершит взаимодействие. Вы получите вердикт Неправильный ответ. Завершите программу, чтобы избежать получения других вердиктов.
Когда вы определите загаданную перестановку, выведите «! p[1] p[2] ... p[n]». Если перестановка определена верно, интерактор выведет «1». В противном случае интерактор выведет «-1» и завершит взаимодействие. Вы получите вердикт Неправильный ответ. Убедитесь, что вы сразу же вышли, чтобы избежать получения других вердиктов.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы:
Для взлома используйте следующий формат теста:
Первая строка должна содержать одно целое число \(t\) (\(1 \leq t \leq 1000\)) — количество наборов входных данных.
Первая строка каждого набора входных данных должна содержать одно целое число \(n\) (\(20 \leq n \leq 100000\)) — длину секретной перестановки.
Следующая строка должна содержать \(n\) целых чисел \(p[1],p[2],p[3],\ldots,p[n]\) такие, что \(p[1]<p[2]\) и \(p\) — перестановка чисел от \(1\) до \(n\).
Вы должны убедиться, что сумма \(n\) по всем тестовым примерам не превышает \(100000\).
Примечание
Загаданная перестановка — \(\{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}\).
Для первого запроса значениями \((a,b,c)\) являются \((1,5,2)\). Поскольку \(p[1]=9\), \(p[5]=16\) и \(p[2]=10\), то возвращаемое значение — медиана \(\{|9-16|,|16-10|,|9-10|\}\), которая равна \(6\).
Для второго запроса значения \((a,b,c)\) равны \((20,19,2)\). Поскольку \(p[20]=1\), \(p[19]=13\) и \(p[2]=10\). Возвращаемое значение — медиана \(\{|1-13|,|13-10|,|1-10|\}\), которая равна \(9\).
Каким-то чудом мы выяснили, что загаданная перестановка — \(\{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}\). Мы выводим ее и получаем от интерактора \(1\), что означает, что мы правильно угадали перестановку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
20
6
9
1
|
? 1 5 2
? 20 19 2
! 9 10 19 7 16 18 11 14 15 6 20 8 17 4 5 3 12 2 13 1
|