Esta es una tarea de comunicación. Tenga en cuenta que solo se permite C++ para esta tarea.

Takina y Chisato están en una convención de frutas. Después de un día de tomar fotos con sus cosplayers de frutas favoritos, se encontraron con un puesto de juegos.

Las reglas del juego son las siguientes:

• Hay $n$ frutas, cada una con una etiqueta distinta del 1 al $n$.
• Exactamente una de las frutas es un limón, pero ni Takina ni Chisato saben todavía cuál es.
• Takina recibirá todas las $n$ frutas una por una. Su objetivo es comunicar la etiqueta del limón a Chisato (quien está vendada durante este proceso).

Antes de recibir cualquier fruta, a Takina se le entrega un arreglo $p$, que representa el orden en el que aparecerán las etiquetas de las frutas. $p[1]$ será la etiqueta de la primera fruta, $p[2]$ será la etiqueta de la segunda fruta, y así sucesivamente. Luego, Takina escribirá una cadena binaria $b$ que contiene solo 0s y 1s. La cadena no debe tener más de 5000 caracteres, pero puede estar vacía. Sea $x$ la longitud de $b$.

Posteriormente, las frutas se entregan a Takina una por una en el orden mencionado. Al recibir cada fruta, se le informa a Takina si es el limón.

• Si la fruta no es el limón, Takina puede elegir si comerla o no. Esta decisión debe tomarse antes de recibir la siguiente fruta y no puede cambiarse.
• Si la fruta es el limón, Takina no debe comerla.

Sea $y$ el número total de frutas comidas por Takina.

Finalmente, Chisato recibe la cadena $b$ y la lista ordenada de etiquetas de las frutas que no fueron comidas. Usando esta información, Chisato debe determinar la etiqueta de la fruta que es el limón.

Takina y Chisato han decidido jugar este juego $t$ veces. Diseñe una estrategia para que identifiquen correctamente el limón mientras minimizan tanto $x$ como $y$.

Detalles de implementación

Esta es una tarea de comunicación. No lea de la entrada estándar ni escriba en la salida estándar.

Necesita implementar tres procedimientos.

Para Takina, debe implementar:

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

• subtask: el índice de la subtarea a la que pertenece el caso de prueba.
• n: el número de frutas.
• p: un arreglo de longitud $n + 1$ donde:
  • $p[0] = 0$, y
  • para cada $1 \le i \le n$, $p[i]$ es la etiqueta de la $i$-ésima fruta que se le entregará a Takina.
• Este procedimiento se llama $t$ veces por caso de prueba, una vez al inicio de cada juego.

Este procedimiento debe devolver la cadena $b$, con una longitud entre 0 y 5000 inclusive, que consiste solo en 0s y 1s. Si se devuelve una cadena de longitud o formato inválido, recibirá un veredicto de Wrong Answer.

bool receive_fruit(int id, bool is_lemon)

• id: la etiqueta de la fruta entregada a Takina.
• is_lemon: true si la fruta entregada es el limón, false en caso contrario.
• Este procedimiento se llama $n$ veces para cada uno de los $t$ juegos, una vez por cada fruta.

Este procedimiento debe devolver true si la fruta debe ser comida, y false en caso contrario. Si se devuelve true cuando is_lemon es true, recibirá un veredicto de Wrong Answer.

Para Chisato, debe implementar:

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

• subtask: el índice de la subtarea a la que pertenece el caso de prueba.
• n: el número de frutas.
• b: la cadena devuelta por init.
• uneaten: el vector ordenado de longitud $n - y + 1$ de las etiquetas de las frutas no comidas por Takina, donde:
  • uneaten[0] = 0, y
  • uneaten[i] es la $i$-ésima etiqueta más pequeña entre las frutas no comidas.
• Este procedimiento se llama $t$ veces por caso de prueba, una vez al final de cada juego.

Este procedimiento debe devolver un entero, la etiqueta del limón. Si el valor de retorno no coincide con la etiqueta correcta, recibirá un veredicto de Wrong Answer.

En la evaluación real, un programa que llama a los procedimientos anteriores se ejecuta dos veces:

1. En la primera ejecución, se realizan los siguientes pasos $t$ veces:
   • Se llama a init una vez.
   • Se llama a receive_fruit $n$ veces, siguiendo el orden de las frutas entregadas a Takina.
   • Su programa puede almacenar y retener información a través de llamadas sucesivas.
2. En la segunda ejecución, el orden de los juegos puede ser diferente al de la primera ejecución. Para cada uno de los $t$ juegos:
   • Se llama a answer una vez. Aparte de los parámetros pasados a answer, su programa no puede acceder a información de la primera ejecución.

Dado que el procedimiento puede ser llamado más de una vez, debe prestar atención al efecto de los datos restantes de la llamada anterior en la llamada actual.

Subtareas

Para todos los casos de prueba, la entrada satisfará los siguientes límites:

• $1 \le t \le 10\,000$
• $n = 500$
• $1 \le p[i] \le n$ para todo $1 \le i \le n$
• Hay exactamente un limón.

Para cada subtarea, su programa será calificado de manera diferente según la longitud de la cadena que escribe Takina, $x$, y el número de frutas que come, $y$. Su puntuación para cada caso de prueba se calcula utilizando el valor máximo de $x$ en todos los $t$ juegos y el valor máximo de $y$ en todos los $t$ juegos.

Interacción de ejemplo

Considere un solo juego ($t = 1$) con $n = 4$. Tenga en cuenta que esto no satisface las restricciones de entrada y solo se utiliza aquí con fines de demostración.

Suponga que a Takina se le entrega el orden de frutas $p = [0, 3, 1, 4, 2]$. Esto significa que las frutas se presentarán en el siguiente orden de etiquetas: 3, 1, 4, 2. Suponga que la fruta con la etiqueta 4 es el limón.

Primero, se llama a init. Takina recibe los parámetros subtask, n y p, y devuelve la cadena b.

Luego, se llama a receive_fruit una vez por cada fruta en el orden dado. Cada vez, se le informa a Takina si la fruta es el limón y decide si comerla.

Finalmente, Chisato recibe la cadena b y el conjunto ordenado de etiquetas de las frutas que no fueron comidas, y se llama al procedimiento answer.

Una posible secuencia de llamadas y valores de retorno se muestra a continuación:

En este ejemplo, Takina come las frutas con las etiquetas 3 y 2, por lo que las frutas no comidas son {1, 4}. El vector uneaten pasado a answer es por lo tanto [0, 1, 4].

Usando b y uneaten, el procedimiento answer devuelve 4, que es la etiqueta del limón. Esta estrategia fue capaz de identificar correctamente el limón con $x = 3$ y $y = 2$.

Pruebas

Puede descargar el evaluador de muestra (grader.cpp), el archivo de cabecera (lemon.h) y una plantilla de solución (lemon.cpp) en los archivos adjuntos. Se proporcionan dos archivos de entrada para sus pruebas, sample1.txt y sample2.txt. Puede usar los scripts compile.sh para compilar y run.sh para ejecutar su solución para las pruebas.

Las pruebas de usuario de CMS no son compatibles para este problema.

Evaluador de muestra

Se proporciona un evaluador de muestra para ayudarle a probar su implementación localmente. A diferencia del evaluador oficial, el evaluador de muestra ejecuta su programa solo una vez y no altera el orden de las pruebas para Takina y Chisato.

Formato de entrada

La primera línea de la entrada contiene un entero subtask. La segunda línea de la entrada contiene un entero t.

Las siguientes $t$ líneas de la entrada describen cada una un juego. Cada juego se describe mediante:

• una línea que contiene dos enteros separados por espacios $n$ y $l$, que representan el número de frutas y la etiqueta del limón, y
• una línea que contiene $n$ enteros separados por espacios $p[1], p[2], \dots, p[n]$.

Formato de salida

El evaluador de muestra genera un único número real que representa la fracción de puntuación calculada a partir de los valores de $x$ e $y$ en todos los juegos.

Nota

Se pueden imprimir mensajes de diagnóstico adicionales en la salida de error estándar. El evaluador de muestra no simula el comportamiento del evaluador oficial.