Este é um problema interativo.

No balcão da loja de sobremesas da Pulga, estão dispostas duas filas de gelatinas coloridas com duas camadas (a camada superior é $a$ e a inferior é $b$). Devido à regra de «solidificação complementar» da loja, a soma das alturas das camadas superior e inferior de cada gelatina é exatamente $n+1$. Originalmente, os funcionários tinham organizado cada uma das duas filas, pelas alturas, numa permutação perfeita de $1 \sim n$, mas, na noite passada, um animado funcionário pulga trocou acidentalmente as camadas superior e inferior em algumas posições!

Agora, o festival anual de sobremesas está prestes a começar, e os funcionários precisam de reconstruir a disposição inicial das gelatinas antes dessas trocas (ou seja, a sequência $a$ das alturas da camada superior antes das trocas).

Não podes observar diretamente as alturas das gelatinas, mas podes enviar instruções ao aparelho de medição automático da loja: especifica algumas posições $i$, e o aparelho trocará as camadas superior e inferior nessas posições e devolverá a diferença entre a maior e a menor altura (amplitude) da camada superior atual, assim como a diferença entre a maior e a menor altura (amplitude) da camada inferior. Atenção: o efeito de cada troca é mantido.

Consegues reconstruir a sequência original das gelatinas da camada superior com um número limitado de medições com trocas?

A biblioteca de interação começa por escolher uma permutação $p$ de $1\sim n$ e construir a permutação $b_i=n+1-p_i$. Depois, para cada índice $i$, a biblioteca decide independentemente se troca os dois números na posição $i$. Denotamos por $a,b$ os vetores obtidos após essas trocas. Nesse momento, temos sempre $a_i+b_i=n+1$, mas $a,b$ podem já não ser permutações.

Conheces $n$, mas não conheces estes dois vetores. Podes escolher algumas posições e trocar $a_i,b_i$ nessas posições; a biblioteca de interação informa-te das amplitudes dos dois vetores após as trocas. O efeito de cada troca é mantido.

A tua tarefa é reconstruir o vetor $a$ antes da primeira consulta. A resposta também é considerada correta se só coincidir com o vetor pretendido depois de se substituir simultaneamente cada valor $x$ do vetor devolvido por $n+1-x$.

Detalhes de implementação

Não precisas de implementar a função main, nem deves fazê-lo.

Deves incluir o cabeçalho range.h no ficheiro-fonte recover.cpp e implementar a seguinte função:

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

• $c$ é o número da subtarefa atual; nos testes oficiais, assume os valores $1,2,3,4$, e no exemplo assume o valor $0$. $n$ é o comprimento dos vetores. A biblioteca de interação chama recover exatamente uma vez por caso de teste.
• O valor devolvido deve ser um vetor de inteiros de comprimento $n$, representando $a$ antes da primeira consulta ou o seu complemento global.

Podes chamar a seguinte função:

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

• Os índices em positions devem ser distintos entre si e pertencer a $[0,n-1]$. É permitido passar um vetor vazio.
• A biblioteca de interação troca os valores atuais $a_i,b_i$ exatamente uma vez em cada índice indicado em positions e depois devolve a amplitude do vetor $a$ atual e a amplitude do vetor $b$ atual. As trocas entre consultas são cumulativas, mas, ao devolver a resposta, deves reconstruir o vetor inicial, anterior às trocas.
• A amplitude é definida como o valor máximo do vetor menos o seu valor mínimo. Como temos sempre $b_i=n+1-a_i$, as duas amplitudes são necessariamente iguais.
• O número de chamadas a query não pode exceder o limite $Q_{\max}$ do caso de teste em questão.

A biblioteca de interação não é adaptativa: os vetores iniciais são fixados antes do início de recover e não são alterados em função das consultas do participante. A biblioteca usada na avaliação final pode ser diferente da biblioteca de exemplo fornecida. O teu programa não pode ler os dados internos da biblioteca nem operar diretamente sobre os fluxos de entrada e saída padrão.

Testes locais

Coloca recover.cpp, range.h e o ficheiro grader.cpp fornecido nos anexos no mesmo diretório e compila com C++17:

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

A primeira linha lida pela biblioteca de interação local contém $c,n,Q_{\max}$; a segunda contém a permutação $p_0,\ldots,p_{n-1}$; a terceira contém $n$ números $0/1$, em que $1$ indica que essa posição é trocada antes do início da interação. Apenas $c,n$ são fornecidos ao participante através dos argumentos da função; a permutação, os indicadores de troca e o limite de consultas não são transmitidos diretamente ao programa do participante.

Se a resposta estiver correta, a biblioteca local imprime Correct! na primeira linha e Queries used: Q na segunda, em que $Q$ é o número de consultas usadas nesta chamada. Se a resposta estiver incorreta, imprime Wrong answer.; se uma chamada à interface for inválida, também apresenta o motivo do erro no fluxo de erro padrão.

Exemplos

Entrada 1

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

Saída 1

Correct!
Queries used: 16

Nota

No exemplo, antes do início da interação, $a=(3,6,1,4,5,5)$; o seu complemento global é $(4,1,6,3,2,2)$. Devolver qualquer um destes vetores é correto. A primeira chamada a query({}) devolve $(5,5)$. A saída acima corresponde à execução do programa de referência fornecido nos anexos; o número de consultas pode variar entre programas corretos.

Restrições

Para todos os dados de teste, $1\le n\le 500$.

A pontuação de cada subtarefa é determinada pelo caso de teste com o menor multiplicador de pontuação, conforme descrito abaixo.

Pontuação

Se a resposta devolvida por recover estiver incorreta, os argumentos de query forem inválidos ou o número de consultas exceder $Q_{\max}$, a pontuação desse caso de teste é $0$.

Caso contrário, nas subtarefas $1,2$, o caso de teste recebe a pontuação total. Nas subtarefas $3,4$, seja $Q$ o número de consultas efetivamente usadas nesse caso de teste; o multiplicador de pontuação $f(Q)$ é calculado segundo a tabela seguinte:

A pontuação da subtarefa $3$ é $40f(Q)$ e a pontuação da subtarefa $4$ é $40f(Q)$. A pontuação final é arredondada para $3$ casas decimais.

Limite de tempo: $2\ \mathrm{s}$.

Limite de memória: $512\ \mathrm{MiB}$.