Este es un problema interactivo.

En vísperas de la inauguración del festival de postres, el chef está dando forma con esmero a la creación emblemática de la tienda: «千层幻彩慕斯». Este postre se compone de $n$ porciones de mousse de distintos sabores, numeradas $0,1,\dots,n-1$.

Sin embargo, en medio del ajetreo, el ayudante ha confundido accidentalmente el orden de las porciones de mousse. Ahora están dispuestas en una fila de izquierda a derecha, formando una permutación desconocida de posiciones $p=(p_0,p_1,\dots,p_{n-1})$, donde $p_i$ representa el número de la porción de mousse situada en la posición $i$.

Para determinar la posición exacta de cada porción de mousse, puedes utilizar un dispositivo de pruebas de postres. Cada vez que eliges tres posiciones distintas entre sí $x,y,z$, el dispositivo devuelve la suma del menor y el mayor número de las tres porciones de mousse:

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

La campana de inauguración está a punto de sonar. ¿Puedes reconstruir con precisión la verdadera posición de cada porción de mousse mediante un número limitado de pruebas?

Hay una permutación de longitud $n$, denominada $p$, cuyos elementos son exactamente $0,1,\ldots,n-1$. No conoces el contenido de $p$.

Puedes elegir tres índices distintos entre sí $x,y,z$, y la biblioteca de interacción devolverá

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

Tu tarea es reconstruir la permutación completa. El límite de consultas y la manera de calcular la puntuación según el número de consultas se indican más adelante.

Detalles de implementación

No necesitas implementar la función main, ni debes hacerlo. El archivo fuente que envíes debe incluir:

#include "mousse.h"

Debes implementar las siguientes dos funciones:

void init(int c);
std::vector<int> mousse(int c, int n);

• $c$ es el número de la subtarea; $c=0$ indica el ejemplo. Cada caso de prueba contiene exactamente una instancia. La biblioteca de interacción llama una vez a init(c) para ese caso de prueba y, a continuación, una vez a mousse(c,n).
• mousse debe devolver un arreglo de longitud $n$ cuyo elemento de índice $i$ sea $p_i$; los índices comienzan en $0$.

Puedes llamar a la siguiente función para realizar una consulta:

int query(int x, int y, int z);

Debe cumplirse $0\le x,y,z < n$, y $x,y,z$ deben ser distintos dos a dos. La función devuelve $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$.

Pruebas del programa

Los archivos adjuntos incluyen mousse.h, la biblioteca de interacción local grader.cpp y el programa de ejemplo template_mousse.cpp. Guarda tu programa como mousse.cpp; puedes ejecutar los siguientes comandos en el directorio de este problema:

g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.in

La biblioteca de interacción local lee la permutación oculta de la entrada estándar; tu programa no debe leer estos datos por su cuenta. El formato de entrada es el siguiente:

• La primera línea contiene dos enteros $c,n$.
• La segunda línea contiene $p_0,p_1,\ldots,p_{n-1}$.

Si la respuesta es correcta, la biblioteca de interacción imprime Correct! y Max queries used: Q, donde $Q$ es el número de consultas realizadas en ese caso de prueba; si la respuesta es incorrecta, imprime Wrong answer.. Si se realiza una consulta no válida o se supera el límite de consultas, el programa imprime un mensaje de error en la salida de error estándar y termina. Puedes añadir el argumento -v para ver el número de consultas de ese caso de prueba.

Ejemplos

Entrada 1

0 10
0 2 9 1 5 8 3 7 6 4

Salida 1

Correct!
Max queries used: 15

Nota

Por ejemplo, al llamar a query(0,1,2), los tres valores correspondientes son $0,2,9$, y se devuelve $0+9=9$. El programa de referencia utiliza $15$ consultas en esta instancia. Si utilizas otra estrategia, este número puede ser diferente.

Restricciones

Para todos los datos de prueba, $n\in\{10,100,10^5\}$, y $p$ es una permutación de $0\sim n-1$. Cada caso de prueba contiene exactamente una instancia.

En el ejemplo, $c=0$ y $n=10$, y el límite de consultas es $1000$.

Subtareas

Ten en cuenta lo siguiente:

• La biblioteca de interacción no es adaptativa. La permutación de cada caso de prueba está determinada antes de llamar a tu programa y no cambia en función de las consultas.
• No debes obtener la permutación oculta leyendo la entrada estándar ni mediante otros métodos no permitidos. La implementación de la biblioteca de interacción utilizada en la evaluación final puede ser diferente de la biblioteca local.

Si, en un caso de prueba, mousse devuelve una respuesta incorrecta, los argumentos de query no son válidos o el número de consultas supera el $Q_{\max}$ de esa subtarea, el multiplicador de puntuación de ese caso de prueba es $0$.

En las subtareas $1,2$, solo se obtiene la puntuación completa de la subtarea si todos los casos de prueba son correctos.

Para las subtareas $3,4$, si el multiplicador de puntuación de cualquier caso de prueba es $0$, la subtarea recibe $0$ puntos. En caso contrario, sea $Q$ el máximo número de consultas entre todos los casos de prueba de esa subtarea. El multiplicador de puntuación $f(Q)$ se determina mediante la siguiente tabla:

Si $Q\le 99970$, entonces $f(Q)=100\%$. Si $Q$ se encuentra entre dos filas consecutivas de la tabla, $(Q_i,f_i)$ y $(Q_{i+1},f_{i+1})$, entonces:

$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$

La puntuación de la subtarea $3$ es $30f(Q)$ y la de la subtarea $4$ es $60f(Q)$. La puntuación final se redondea a $3$ cifras decimales.

Límite de tiempo: $10\ \mathrm{s}$.

Límite de memoria: $512\ \mathrm{MiB}$.