Это интерактивная задача.

Условие задачи

Вы увлеклись игрой-головоломкой. На этом уровне игры ваша задача — открыть сундук с сокровищами.

У вас есть $n$ ключей, пронумерованных от $0$ до $n-1$, и $n$ пазов на сундуке, также пронумерованных от $0$ до $n-1$. Ваша задача — собрать подсказки, вставить ключи в пазы в правильном порядке, а затем нажать на переключатель, чтобы открыть сундук. Этот правильный порядок ключей можно представить как перестановку $p$ длины $n$ (индексация с $0$), где $p_i$ — это номер ключа, который должен быть вставлен в паз $i$.

Ваша попытка может быть представлена как перестановка $q$ длины $n$, означающая, что в паз $i$ вы вставляете ключ $q_i$. Если для каждого $0 \le i \le n-1$ выполняется $p_i=q_i$, то ваша попытка верна, вы открываете сундук и успешно проходите уровень; в противном случае попытка считается неудачной. У вас есть только одна попытка открыть сундук, поэтому будьте предельно осторожны.

После тщательного наблюдения вы обнаружили секрет сундука: на задней стороне есть скрытая кнопка. После того как вы задали перестановку $q$ и вставили ключи в пазы, вы можете нажать на скрытую кнопку, и сундук сообщит, сколько ключей установлено правильно — то есть сколько существует индексов $0 \le i \le n-1$, для которых $p_i=q_i$. Назовем эту операцию запросом. Вы можете изменять свою перестановку $q$ и выполнять запросы многократно, прежде чем нажать финальный переключатель, пока не соберете достаточно информации, чтобы определить правильную перестановку $p$.

Однако, исходя из сложности и интереса игры, существует особое правило: количество запросов к сундуку не должно превышать $20000$. Если вы превысите этот лимит, сундук будет заблокирован навсегда, что означает проигрыш. Успех в игре зависит от вашего мастерства!

Детали реализации

Вам не нужно и не следует реализовывать функцию main. В начале вашей программы необходимо добавить #include "puzzle.h" и реализовать следующую функцию:

void play(int n);

• Здесь $n$ — длина перестановки.
• В процессе работы интерактивной библиотеки эта функция будет вызвана ровно один раз.

Вы можете вызывать следующие две функции:

int query(const std::vector<int> &q);

• Здесь $q$ должна быть перестановкой длины $n$, то есть длина $q$ должна быть равна $n$, и все целые числа от $0$ до $n-1$ должны встречаться в $q_0 \sim q_{n-1}$ ровно один раз.
• Функция сравнит предложенную вами перестановку $q$ с правильной перестановкой $p$ и вернет результат запроса, то есть количество целых чисел $i$, таких что $0 \leq i \leq n-1$ и $p_i = q_i$.
• Количество вызовов этой функции не должно превышать $20000$.

void check(const std::vector<int> &q);

• Здесь $q$ должна быть перестановкой длины $n$, то есть размер $q$ должен быть равен $n$, и все целые числа от $0$ до $n-1$ должны встречаться в $q_0 \sim q_{n-1}$ ровно один раз.
• Эта функция должна быть вызвана ровно один раз во время выполнения вашей функции play.
• Функция сравнит предложенную вами перестановку $q$ с правильной перестановкой $p$. Если $p=q$, ваш ответ считается верным, в противном случае — неверным.
• В любом случае, после выполнения этой функции интерактивная библиотека выведет соответствующую информацию и немедленно завершит работу.

Вы должны гарантировать, что аргументы, передаваемые при вызове функций query или check, соответствуют вышеуказанным требованиям.

Вы можете ознакомиться с прилагаемым файлом эталонной интерактивной библиотеки для получения дополнительных сведений о реализации.

Тестирование программы

В прилагаемых файлах предоставлена эталонная реализация интерактивной библиотеки grader.cpp. Реализация интерактивной библиотеки, используемая при финальном тестировании, отличается от этой, поэтому решение участника не должно зависеть от деталей реализации интерактора.

Предположим, что ваш исходный файл называется puzzle.cpp. Вам нужно поместить прилагаемые файлы в ту же директорию, что и исходный файл, и использовать следующую команду для компиляции:

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -lm

При запуске полученного исполняемого файла:

• Исполняемый файл будет считывать данные из стандартного ввода в следующем формате:

  • Первая строка: целое число $n$, длина перестановки. Гарантируется, что $2 \leq n \leq 1000$;
  • Вторая строка: $n$ целых чисел $p_0, p_1, \dots, p_{n-1}$, представляющих правильную перестановку. Гарантируется, что $p_0, \dots, p_{n-1}$ — это перестановка длины $n$, то есть все целые числа от $0$ до $n-1$ встречаются ровно один раз.

• После завершения чтения интерактивная библиотека проведет тестирование с этими данными и выведет следующее:

  • Если ваша программа работает корректно, количество вызовов функции query не превышает $20000$, и при вызове функции check была передана правильная перестановка, будет выведено:

    Correct.
    cnt = x

    где $x$ — количество вызовов функции query вашей программой.

  • В противном случае будет выведено соответствующее сообщение об ошибке.

Примеры

Пример 1

Входные данные 1

3
1 0 2

Выходные данные 1

Correct.
cnt = 3

Примечание 1

Это возможный вывод при использовании прилагаемого grader.cpp и корректно работающей программы.

Для данного примера возможная последовательность вызовов:

• Вызов query([0, 1, 2]), возвращает $1$;
• Вызов query([0, 2, 1]), возвращает $0$;
• Вызов query([1, 0, 2]), возвращает $3$;
• Вызов check([1, 0, 2]).

Подзадачи

В этой задаче используется пакетное тестирование. Для каждой подзадачи ваш балл равен минимуму баллов за все тесты внутри этой подзадачи.

Для всех тестов $1 \leq n \leq 1000$.

Для первых 6 подзадач, если ваша программа работает корректно, количество вызовов query не превышает $20000$, и при вызове check передана правильная перестановка, вы получаете полный балл за тест.

Для 7-й подзадачи, помимо вышеуказанных условий, вы можете получить дополнительные баллы. Пусть $m$ — количество вызовов query вашей программой, тогда ваш балл рассчитывается следующим образом:

Примечание

Гарантируется, что для любых корректных данных и вызовов в пределах ограничений время работы самой интерактивной библиотеки не превышает $0.2$ с, а используемая память не превышает $128$ МБ.

Заголовочные файлы, необходимые для работы интерактивной библиотеки, уже указаны в прилагаемом файле. Ваша программа может включать любые необходимые ей заголовочные файлы.

Интерактивная библиотека в этой задаче не является адаптивной, то есть правильная перестановка определяется до вызова функции play и не меняется в зависимости от ваших запросов.

Попытки получить баллы путем доступа к файлам ввода-вывода, атаки на систему тестирования или интерактивную библиотеку считаются мошенничеством, и полученные баллы будут аннулированы.