| Технокубок 2018 - Отборочный Раунд 2 |
|---|
| Закончено |
Это интерактивная задача.
Жюри загадало некоторую перестановку p из чисел от 0 до n - 1, про которую вам известна только ее длина n. Напомним, что в перестановке все числа различны.
Пусть b — обратная к p перестановка, то есть pbi = i для всех i. Тогда единственное действие, которое вы можете выполнить — узнать xor элементов pi и bj, указав их индексы i и j (не обязательно различные). В результате запроса для индексов i и j вы получите значение 
, где символом 
обозначена операция xor. Описание операции xor вы можете найти в примечаниях.
Заметим, что некоторые перестановки могут быть неотличимы от заданной, даже если сделать все различные n2 запросов. Вам необходимо вычислить, сколько перестановок неотличимы от загаданной, а также выдать одну из таких перестановок, сделав не более 2n запросов.
Загаданная перестановка не зависит от ваших запросов.
В первой строке входных данных следует целое положительное число n (1 ≤ n ≤ 5000) — длина загаданной перестановки. В первую очередь ваша программа должна прочитать это число.
Когда ваша программа будет готова вывести ответ, выведите три строки.
В первой строке выведите один символ «!».
Во второй строке выведите одно целое число answers_cnt — количество перестановок, неотличимых от загаданной жюри, считая загаданную.
В третьей строке выведите n целых чисел p0, p1, ..., pn - 1 (0 ≤ pi < n, все pi должны быть различны) — одну из перестановок, неотличимых от загаданной жюри.
После вывода ответа ваша программа должна завершиться.
Чтобы узнать xor двух элементов, выведите строку вида «? i j», где i и j — целые числа от 0 до n - 1 — индекс элемента перестановки и индекс элемента обратной перестановки, xor-сумму которых ваша программа запрашивает. После этого выведите перевод строки и сделайте операцию flush.
После выполнения запроса ваша программа может считать целое число, равное .
Для перестановки длины n ваша программа должна сделать не более 2n запросов на xor-сумму. Обратите внимание, что вывод ответа не учитывается при подсчете количества запросов. Обратите внимание, что вы можете задать не более 2n запросов. В случае, если ваша программа сделает больше 2n запросов или сделает хотя бы один некорректный запрос, ваше решение получит вердикт «Неправильный ответ».
Если в какой-то момент ваша программа считывает -1 как ответ, она должна немедленно завершиться (например, вызовом exit(0)). Вы получите вердикт «Неправильный ответ», и это будет означать, что вы задали больше 2n запросов или задали некорректный запрос. Если вы проигнорируете это, то можете получить любой вердикт, так как ваша программа продолжит читать из закрытого потока ввода.
Выше решение получит вердикт «Решение зависло», если вы не будете ничего выводить или забудете сделать операцию flush после вывода вопроса или ответа.
Чтобы выполнить операцию flush, можете использовать (сразу после вывода запроса и перевода строки):
- fflush(stdout) в C++;
- System.out.flush() в Java;
- stdout.flush() в Python;
- flush(output) в Pascal;
- Для других языков смотрите документацию.
Взломы
Используйте следующий формат для взломов:
n
p0 p1 ... pn - 1
Взламываемая программа не будет иметь доступа к этим данным.
3
0
0
3
2
3
2
? 0 0
? 1 1
? 1 2
? 0 2
? 2 1
? 2 0
!
1
0 1 2
4
2
3
2
0
2
3
2
0
? 0 1
? 1 2
? 2 3
? 3 3
? 3 2
? 2 1
? 1 0
? 0 0
!
2
3 1 2 0
Операцией xor, или побитовое исключающее ИЛИ, называется операция над двумя целыми числами, при которой i-й разряд результата в двоичной системе счисления будет равен 1 тогда и только тогда, когда ровно у одного из двух целых чисел в i-м разряде в двоичной системе счисления стоит 1. Больше информации смотрите по ссылке.
В первом примере при p = [0, 1, 2], а значит b = [0, 1, 2], на заданные запросы у этой перестановки совпадают все значения для всех выведенных парах i, j. Кроме этой перестановки не существует других перестановок, подходящих под выданные ответы, поэтому это — ответ.
Ответы на запросы:
-
, -
, -
, -
, -
, -
.
В втором примере при p = [3, 1, 2, 0], а значит b = [3, 1, 2, 0], на заданные запросы у этой перестановки совпадают все значения для всех выведенных пар i, j. Однако кроме нее подходит также перестановка p = [0, 2, 1, 3], b = [0, 2, 1, 3], причем на всех n2 возможных запросов у этих двух перестановок ответы будут совпадать, а у всех остальных перестановок ответы будут другие уже на заданных запросах.
