Это интерактивная задача.
Загадана секретная последовательность \(p_0, p_1, \ldots, p_{n-1}\), являющаяся перестановкой чисел \(\{0,1,\ldots,n-1\}\).
Вам нужно найти два индекса \(i\) и \(j\), таких что \(p_i \oplus p_j\) принимает максимальное значение, где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Чтобы их найти, вы можете делать запросы. Каждый запрос устроен так: вы выбираете произвольные индексы \(a\), \(b\), \(c\) и \(d\) (\(0 \le a,b,c,d < n\)). Затем программа жюри вычисляет \(x = (p_a \mid p_b)\) и \(y = (p_c \mid p_d)\), где \(|\) обозначает операцию побитового ИЛИ. Наконец, вы узнаёте результат сравнения чисел \(x\) и \(y\). Другими словами, вам сообщают, какое из трёх условий выполнено: \(x < y\), \(x > y\) или \(x = y\).
Найдите два индекса \(i\) и \(j\) (\(0 \le i,j < n\)), таких что \(p_i \oplus p_j\) максимально среди всех таких пар, сделав не более \(3n\) запросов. Если существует несколько пар индексов, удовлетворяющих условию, выведите любую из них.
Протокол взаимодействия
Первая строка каждого набора входных данных содержит единственное число \(n\) (\(2 \le n \le 10^4\)). В этот момент загадывается перестановка \(p_0, p_1, \ldots, p_{n-1}\). В этой задаче решение жюри неадаптивно. Иначе говоря, последовательность \(p\) фиксирована в каждом наборе входных данных и не будет меняться в процессе взаимодействия с программой участника.
Чтобы сделать запрос, вам нужно выбрать четыре индекса \(a\), \(b\), \(c\) и \(d\) (\(0 \le a,b,c,d < n\)) и вывести строку следующего вида:
После этого вы получите:
- «<», если \((p_a \mid p_b) < (p_c \mid p_d)\);
- «=», если \((p_a \mid p_b) = (p_c \mid p_d)\);
- «>», если \((p_a \mid p_b) > (p_c \mid p_d)\).
Вы можете сделать не более \(3n\) запросов такого вида.
Затем, если ваша программа нашла пару индексов \(i\) и \(j\) (\(0 \le i, j < n\)), такую что \(p_i \oplus p_j\) максимально, выведите строку следующего вида:
Обратите внимание, что эта строка не считается запросом и не учитывается при подсчёте числа сделанных запросов.
После этого переходите к обработке следующего набора входных данных.
Если вы делаете больше \(3n\) запросов, ваша программа должна немедленно завершиться, в таком случае вы получите вердикт Wrong Answer. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение продолжит читать из закрытого потока данных.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Гарантируется, что сумма значений \(n\) по всем наборам входных данных не превосходит \(10^4\).
Взломы
Чтобы делать взломы, используйте следующий формат.
В первой строке находится одно целое число \(t\) (\(1 \le t \le 10^3\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(2 \le n \le 10^4\)).
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(p_0,p_1,\ldots,p_{n-1}\), которые задают перестановку чисел от \(0\) до \(n - 1\).
Сумма значений \(n\) по всем наборам входных данных не должна превышать \(10^4\).
Примечание
В первом наборе входных данных загадана перестановка \(p=[0,3,1,2]\).
На запрос «? 0 2 3 1» решение жюри выведет «<», поскольку \((p_0 \mid p_2) = (0 \mid 1) =1 < (p_3 \mid p_1) = (2 \mid 3) = 3\).
На запрос «? 1 1 2 3» решение жюри выведет «=», поскольку \((p_1 \mid p_1) = (3\mid 3)= 3 = (p_2 \mid p_3) = (1 \mid 2)=3\).
На запрос «? 1 2 0 3» решение жюри выведет «>», поскольку \((p_1 \mid p_2) = (3 \mid 1) = 3 > (p_0 \mid p_3) = (0\mid 2)=2\).
Ответ \(i = 3\) и \(j = 2\) корректен: \((p_3 \oplus p_2) = (2 \oplus 1) = 3\), и это значение максимально среди всех пар \(p_i \oplus p_j\). Другим корректным ответом также является пара \(i=0\) и \(j=1\). Поскольку число запросов не превысило \(3n=12\), ответ считается верным.
Во втором наборе входных данных \(n = 2\), значит, \(p\) есть либо \([0, 1]\), либо \([1, 0]\). В любом случае \(p_0 \oplus p_1 = 1\) максимально возможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
<
=
>
2
|
? 0 2 3 1
? 1 1 2 3
? 1 2 0 3
! 3 2
! 0 1
|