Это сложная версия задачи. Единственное различие между версиями - ограничение на количество запросов. В этой версии вы можете сделать не более 57 запросов. Вы можете делать взломы, только если решены обе версии задачи.
Это интерактивная задача!
salyg1n дал вам целое положительное число \(k\) и решил сыграть с вами в игру. Он загадал массив из \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\)). Вы должны вывести \(a_1 \oplus a_2 \oplus \ldots \oplus a_n\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ. Вы можете делать запросы вида:
- \(?\) \(i\): в ответ на этот запрос вы получите \(a_i \oplus a_{i + 1} \oplus \ldots \oplus a_{i + k - 1}\). Также после этого запроса подотрезок \(a_i, a_{i + 1}, \ldots, a_{i + k - 1}\) развернется, то есть загаданный массив \(a\) станет таким: \(a_1, a_2, \ldots a_{i - 1}, a_{i + k - 1}, a_{i + k - 2}, \ldots, a_{i + 1}, a_i, a_{i + k}, \ldots, a_n\).
Вы можете сделать не более \(57\) запросов чтобы дать ответ на задачу.
Протокол взаимодействия
Взаимодействие Вашей программы с программой жюри в каждом тестовом случае начинается со считывания двух целых положительных четных чисел \(n\) и \(k\) (\(1 \leq k \leq n \leq k^2 \leq 2500\)) – длины загаданного массива и длины подотрезка запроса соответственно.
Чтобы узнать значение \(a_i \oplus a_{i + 1} \oplus \ldots \oplus a_{i + k - 1}\), выведите запрос в формате \(?\) \(i\) (\(1 \leq i \leq n - k + 1\)). Затем считайте одно целое число – ответ на ваш запрос.
Вы можете сделать не более \(57\) запросов. Когда вы будете готовы сообщить ответ, выведите его в формате \(!\) \(x\). После этого следует приступать к обработке следующего тестового случая или завершить программу, если это был последний тестовый случай. Вывод ответа не считается как один из \(57\) запросов.
Если ваша программа сделает более \(57\) запросов для одного набора входных данных, или сделает некорректный запрос, то ответом на запрос будет -1, после получения такого ответа ваша программа должна немедленно завершится, чтобы получить вердикт Неправильный ответ. Иначе она может получить любой другой вердикт.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Гарантируется, что сумма
\(n\) по всем тестовым случаям не превосходит
\(10000\). Интерактор в этой задаче не является адаптивным.
Взломы:
Чтобы сделать взлом, используйте следующий формат:
В первой строке находится одно целое число \(t\) – количество тестовых случаев.
Описание каждого тестового случая должно состоять из двух строк. В первой строке находятся числа \(n\) и \(k\) – длина загаданного массива и длина подотрезка запроса соответственно. Во второй строке находятся \(n\) чисел \(a_1, a_2, \ldots, a_n\) – массив, который должно загадать жюри в данном тестовом случае.
Примечание
В первом тестовом случае жюри загадало массив \(a\) \(=\) \([4, 2, 5, 1]\)
Во втором тестовом случае жюри загадало массив \(a\) \(=\) \([5, 7, 1, 3, 3, 7]\)