Это усложненная версия задачи. Две версии отличаются ограничением на число запросов. Вы можете взламывать по этой задаче только если обе версии решены.
Это интерактивная задача.
У Ridbit есть массив \(a\) из \(n\) целых хочет, и он хочет, чтобы Ashish его отгадал. \(n\) является степенью двойки. Ashish может спрашивать запросы трех видов. Они могут быть вида
- AND \(i\) \(j\) — узнать побитовое И элементов \(a_i\) и \(a_j\) \((1 \leq i, j \le n\), \(i \neq j)\)
- OR \(i\) \(j\) — узнать побитовое ИЛИ элементов \(a_i\) и \(a_j\) \((1 \leq i, j \le n\), \(i \neq j)\)
- XOR \(i\) \(j\) — узнать побитовое исключающее ИЛИ элементов \(a_i\) и \(a_j\) \((1 \leq i, j \le n\), \(i \neq j)\)
Можете ли вы помочь Ashish определить элементы массива?
В этой версии, каждый элемент имеет значение из отрезка \([0, n-1]\) (включительно) и Ashish может спросить не более \(n+1\) запросов.
Протокол взаимодействия
Чтобы сделать запрос, выведите одну из следующих строк (без кавычек):
- «AND i j»;
- «OR i j»;
- «XOR i j»;
где
\(i\) и
\(j\) \((1 \leq i, j \le n\),
\(i \neq j)\) обозначают индексы запроса.
На каждый запрос вы получите в ответ одно целое число \(x\), которое означает значение ответа на ваш вопрос. Если ваш запрос некорректный, вы получите в ответ \(x = -1\). В таком случае вам требуется закончить выполнение программы.
Когда вы угадали элементы массива, вам требуется вывести одну строку, содержащую «!» (без кавычек), после чего должны идти \(n\) разделенных пробелами целых чисел — элементы массива.
Отгадывание массива не считается в числе сделанных запросов.
Интерактор не является адаптивным. Массив \(a\) не меняется с запросами.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Чтобы взломать решение, используйте следующий формат.
В первой строке выведите одно целое число \(n\) \((4 \le n \le 2^{16})\) — длину массива. Она должна быть степенью двойки. В следующий строке должны быть записаны \(n\) разделенных пробелами целых чисел из отрезка \([0, n-1]\) — массив \(a\).
Примечание
Массив \(a\) в первом примере это \([0, 0, 2, 3]\).