Este es un problema interactivo.

En el mostrador de la tienda de postres de las pulgas hay dos filas de gelatinas de dos capas y colores vivos (la capa superior es $a$ y la inferior es $b$). Debido a la regla de «solidificación complementaria» de la tienda, la suma de las alturas de las capas superior e inferior de cada gelatina es exactamente $n+1$. Los empleados habían ordenado ambas filas por altura para formar permutaciones perfectas de $1 \sim n$, ¡pero anoche un animado empleado pulga intercambió accidentalmente las capas superior e inferior en algunas posiciones!

Ahora está a punto de comenzar el festival anual de postres, y los empleados deben recuperar la disposición inicial de las gelatinas anterior a esos intercambios (es decir, la secuencia de alturas $a$ de las capas superiores antes de los intercambios).

No puedes observar directamente las alturas de las gelatinas, pero puedes dar instrucciones al aparato de medición automático de la tienda: indica varias posiciones $i$, y el aparato intercambiará las capas superior e inferior en esas posiciones y devolverá la diferencia entre la altura máxima y la mínima (el rango) de las capas superiores actuales, así como la diferencia entre la altura máxima y la mínima (el rango) de las capas inferiores. Atención: los efectos de cada intercambio se conservan.

¿Puedes recuperar la secuencia inicial de las capas superiores con un número limitado de mediciones con intercambios?

La biblioteca de interacción elige primero una permutación $p$ de $1\sim n$ y construye la permutación $b_i=n+1-p_i$. Después, para cada índice $i$, decide de forma independiente si intercambia los dos números de la posición $i$. Denotamos por $a,b$ los arreglos obtenidos tras completar esos intercambios. Siempre se cumple $a_i+b_i=n+1$, pero $a,b$ ya no son necesariamente permutaciones.

Conoces $n$, pero no conoces estos dos arreglos. Puedes elegir varias posiciones e intercambiar $a_i,b_i$ en ellas; la biblioteca de interacción te indicará los rangos de los dos arreglos después de los intercambios. Los efectos de cada intercambio se conservan.

Tu tarea es recuperar el arreglo $a$ anterior a la primera consulta. También se considera correcta una respuesta si solo coincide con el arreglo objetivo después de sustituir simultáneamente cada valor $x$ del arreglo devuelto por $n+1-x$.

Detalles de implementación

No necesitas ni debes implementar la función main.

Debes incluir el archivo de cabecera range.h en el archivo fuente recover.cpp e implementar la siguiente función:

std::vector<int> recover(int c, int n);

• $c$ es el número de la subtarea actual: toma los valores $1,2,3,4$ en las pruebas oficiales y $0$ en el ejemplo. $n$ es la longitud del arreglo. La biblioteca de interacción llama a recover exactamente una vez por cada caso de prueba.
• El valor devuelto debe ser un arreglo de enteros de longitud $n$ que represente $a$ antes de la primera consulta, o su complemento completo.

Puedes llamar a la siguiente función:

std::pair<int, int> query(const std::vector<int>& positions);

• Los índices de positions deben ser distintos entre sí y pertenecer a $[0,n-1]$. Se permite pasar un arreglo vacío.
• La biblioteca de interacción intercambia los valores actuales $a_i,b_i$ una vez en cada índice de positions y devuelve el rango del arreglo $a$ actual y el rango del arreglo $b$ actual. Los intercambios se acumulan entre consultas, pero al devolver la respuesta debes recuperar el arreglo inicial anterior a los intercambios.
• El rango se define como el valor máximo del arreglo menos su valor mínimo. Puesto que siempre se cumple $b_i=n+1-a_i$, los dos rangos son necesariamente iguales.
• El número de llamadas a query no debe superar el límite $Q_{\max}$ del caso de prueba correspondiente.

La biblioteca de interacción no es adaptativa: los arreglos iniciales se fijan antes de que comience recover y no cambian en función de las consultas del participante. La biblioteca utilizada en la evaluación final puede ser distinta de la biblioteca de ejemplo distribuida. El programa del participante no debe leer datos internos de la biblioteca ni manipular directamente los flujos de entrada o salida estándar.

Pruebas del programa

Coloca recover.cpp, range.h y el archivo adjunto grader.cpp en el mismo directorio y compila con C++17:

g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.in

La primera línea que lee la biblioteca de interacción local contiene $c,n,Q_{\max}$; la segunda contiene la permutación $p_0,\ldots,p_{n-1}$; la tercera contiene $n$ números $0/1$, donde $1$ indica que esa posición se intercambia antes de comenzar la interacción. Solo $c,n$ se proporcionan al participante mediante los parámetros de la función; la permutación, los indicadores de intercambio y el límite de consultas no se pasan directamente al programa del participante.

Si la respuesta es correcta, la biblioteca local imprime Correct! en la primera línea y Queries used: Q en la segunda, donde $Q$ es el número de consultas utilizadas durante esta llamada. Si la respuesta es incorrecta, imprime Wrong answer.; si una llamada a la interfaz no es válida, también indica el motivo en el flujo de error estándar.

Ejemplos

Entrada 1

0 6 67
3 1 6 4 2 5
0 1 1 0 1 0

Salida 1

Correct!
Queries used: 16

Nota

En el ejemplo, antes de comenzar la interacción, $a=(3,6,1,4,5,5)$; su complemento completo es $(4,1,6,3,2,2)$. Devolver cualquiera de los dos es correcto. La primera llamada a query({}) devuelve $(5,5)$. La salida anterior corresponde al resultado de ejecutar el programa de referencia adjunto; otros programas correctos pueden utilizar un número diferente de consultas.

Restricciones

Para todos los datos de prueba, $1\le n\le 500$.

La puntuación de cada subtarea se determina por el caso de prueba que tenga el menor multiplicador de puntuación dentro de ella, tal como se detalla a continuación.

Subtareas

Si la respuesta devuelta por recover es incorrecta, los argumentos de query no son válidos o el número de consultas supera $Q_{\max}$, la puntuación de ese caso de prueba es $0$.

En caso contrario, los casos de prueba de las subtareas $1,2$ reciben la puntuación completa. Para las subtareas $3,4$, sea $Q$ el número de consultas realmente utilizadas en ese caso de prueba. El multiplicador de puntuación $f(Q)$ se calcula según la siguiente tabla:

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

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

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