Это коммуникационная задача. Обратите внимание, что для этой задачи разрешен только C++.

Такина и Чисато находятся на фруктовой ярмарке. После дня фотографирования с их любимыми косплеерами фруктов они наткнулись на игровой стенд.

Правила игры следующие: Есть $n$ фруктов, каждый с уникальной меткой от $1$ до $n$. Ровно один из фруктов — лимон, но ни Такина, ни Чисато пока не знают, какой именно. * Такине будут давать все $n$ фруктов по очереди. Её цель — сообщить метку лимона Чисато (которая во время этого процесса находится с завязанными глазами).

Перед получением фруктов Такине дают массив $p$, который представляет порядок, в котором будут появляться метки фруктов. $p[1]$ будет меткой первого фрукта, $p[2]$ — меткой второго фрукта и так далее. Затем Такина записывает бинарную строку $b$, содержащую только $0$ и $1$. Длина строки не должна превышать $5000$ символов, но она может быть пустой. Пусть $x$ обозначает длину $b$.

После этого фрукты дают Такине по одному в указанном порядке. При получении каждого фрукта Такину информируют, является ли он лимоном. Если фрукт не является лимоном, Такина может выбрать, съесть его или нет. Это решение должно быть принято до получения следующего фрукта и не может быть изменено. Если фрукт является лимоном, Такина не должна его есть.

Пусть $y$ обозначает общее количество фруктов, съеденных Такиной.

Наконец, Чисато получает строку $b$ и отсортированный список меток фруктов, которые не были съедены. Используя эту информацию, Чисато должна определить метку фрукта, который является лимоном.

Такина и Чисато решили сыграть в эту игру $t$ раз. Разработайте стратегию для них, чтобы правильно определить лимон, минимизируя при этом как $x$, так и $y$.

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

Это коммуникационная задача. Не читайте данные из стандартного потока ввода и не пишите в стандартный поток вывода.

Вам необходимо реализовать три процедуры.

Для Такины вы должны реализовать:

std::string init(int subtask, int n, std::vector<int> p)

• subtask: индекс подзадачи, к которой относится тест.
• n: количество фруктов.
• p: массив длины $n + 1$, где:
  • $p[0] = 0$, и
  • для каждого $1 \le i \le n$, $p[i]$ — это метка $i$-го фрукта, который будет дан Такине.
• Эта процедура вызывается $t$ раз для каждого теста, один раз в начале каждой игры.

Эта процедура должна возвращать строку $b$ длиной от $0$ до $5000$ включительно, состоящую только из $0$ и $1$. Если возвращена строка недопустимой длины или формата, вы получите вердикт Wrong Answer.

bool receive_fruit(int id, bool is_lemon)

• id: метка фрукта, данного Такине.
• is_lemon: true, если данный фрукт — лимон, false в противном случае.
• Эта процедура вызывается $n$ раз для каждой из $t$ игр, по одному разу для каждого фрукта.

Эта процедура должна возвращать true, если фрукт следует съесть, и false в противном случае. Если возвращено true, когда is_lemon равно true, вы получите вердикт Wrong Answer.

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

int answer(int subtask, int n, std::string b, std::vector<int> uneaten)

• subtask: индекс подзадачи, к которой относится тест.
• n: количество фруктов.
• b: строка, возвращенная init.
• uneaten: отсортированный вектор длины $n - y + 1$ меток фруктов, не съеденных Такиной, где:
  • uneaten[0] = 0, и
  • uneaten[i] — это $i$-я наименьшая метка среди несъеденных фруктов.
• Эта процедура вызывается $t$ раз для каждого теста, один раз в конце каждой игры.

Эта процедура должна возвращать целое число — метку лимона. Если возвращаемое значение не совпадает с правильной меткой, вы получите вердикт Wrong Answer.

При фактическом тестировании программа, вызывающая вышеуказанные процедуры, запускается дважды:

1. В первом запуске $t$ раз выполняются следующие шаги:
   • Вызывается init.
   • Вызывается receive_fruit $n$ раз, следуя порядку фруктов, данных Такине.
   • Ваша программа может сохранять и использовать информацию между последовательными вызовами.
2. Во втором запуске порядок игр может отличаться от первого запуска. Для каждой из $t$ игр:
   • Вызывается answer. Помимо параметров, переданных в answer, ваша программа не может получать доступ к информации из первого запуска.

Поскольку процедура может быть вызвана более одного раза, вы должны обратить внимание на влияние оставшихся данных от предыдущего вызова на текущий вызов.

Подзадачи

Для всех тестов входные данные будут удовлетворять следующим ограничениям: $1 \le t \le 10\,000$ $n = 500$ $1 \le p[i] \le n$ для всех $1 \le i \le n$ Существует ровно один лимон.

Для каждой подзадачи ваша программа будет оцениваться по-разному в зависимости от длины строки $x$, которую записывает Такина, и количества фруктов $y$, которые она съедает. Ваш балл для каждого теста рассчитывается с использованием максимального значения $x$ во всех $t$ играх и максимального значения $y$ во всех $t$ играх.

Пример взаимодействия

Рассмотрим одну игру ($t = 1$) с $n = 4$. Обратите внимание, что это не удовлетворяет ограничениям ввода и используется здесь только для демонстрационных целей.

Предположим, что Такине дан порядок фруктов $p = [0, 3, 1, 4, 2]$. Это означает, что фрукты будут представлены в следующем порядке меток: $3, 1, 4, 2$. Предположим, что фрукт с меткой $4$ — это лимон.

Сначала вызывается init. Такина получает параметры subtask, $n$ и $p$, и возвращает строку $b$.

Затем вызывается receive_fruit один раз для каждого фрукта в заданном порядке. Каждый раз Такину информируют, является ли фрукт лимоном, и она решает, съесть его или нет.

Наконец, Чисато получает строку $b$ и отсортированный набор меток фруктов, которые не были съедены, и вызывается процедура answer.

Одна из возможных последовательностей вызовов и возвращаемых значений показана ниже:

В этом примере Такина съедает фрукты с метками $3$ и $2$, поэтому несъеденные фрукты — это $\{1, 4\}$. Вектор uneaten, переданный в answer, следовательно, равен $[0, 1, 4]$.

Используя $b$ и uneaten, процедура answer возвращает $4$, что является меткой лимона. Эта стратегия позволила правильно определить лимон при $x = 3$ и $y = 2$.