Este é um problema interativo.
Na véspera da abertura do festival de sobremesas, o chef está a aperfeiçoar cuidadosamente a criação emblemática da loja — a “千层幻彩慕斯”. Esta sobremesa é composta por $n$ porções de mousse com sabores diferentes, numeradas $0,1,\dots,n-1$.
Porém, no meio da confusão, o assistente trocou acidentalmente a ordem das porções de mousse. Agora estão alinhadas da esquerda para a direita, formando uma permutação desconhecida de posições $p=(p_0,p_1,\dots,p_{n-1})$, em que $p_i$ representa o número da porção de mousse colocada na posição $i$.
Para determinar a posição exata de cada porção de mousse, pode utilizar um aparelho de teste de sobremesas. Sempre que selecionar três posições distintas entre si $x,y,z$, o aparelho devolverá a soma do menor e do maior número entre essas três porções de mousse:
$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$
O sino da abertura está prestes a tocar. Conseguirá reconstruir com precisão a verdadeira posição de cada porção de mousse através de um número limitado de testes?
Existe uma permutação $p$ de comprimento $n$, cujos elementos são exatamente $0,1,\ldots,n-1$. Não conhece o conteúdo de $p$.
Pode escolher três índices distintos entre si $x,y,z$, e a biblioteca de interação devolverá
$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$
A sua tarefa é reconstruir toda a permutação. O limite de consultas e a forma de calcular a pontuação em função do número de consultas são apresentados abaixo.
Detalhes de implementação
Não precisa de implementar a função main, nem deve fazê-lo. O ficheiro de código-fonte submetido deve conter:
#include "mousse.h"Deve implementar as duas funções seguintes:
void init(int c);
std::vector<int> mousse(int c, int n);- $c$ é o número da subtarefa; $c=0$ indica o exemplo. Cada caso de teste contém exatamente uma instância. Para esse caso de teste, a biblioteca de interação chama
init(c)uma vez e, em seguida, chamamousse(c,n)uma vez. moussedeve devolver um vetor de comprimento $n$, cujo elemento no índice $i$ é $p_i$, com índices a começar em $0$.
Pode chamar a função seguinte para efetuar uma consulta:
int query(int x, int y, int z);É necessário que $0\le x,y,z < n$ e que $x,y,z$ sejam distintos dois a dois. A função devolve $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$.
Como testar o programa
Os anexos incluem mousse.h, a biblioteca de interação local grader.cpp e o programa de exemplo template_mousse.cpp. Guarde o seu programa como mousse.cpp; no diretório deste problema, pode executar:
g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.inA biblioteca de interação local lê a permutação oculta da entrada padrão. O programa do participante não pode ler esses dados por si próprio. O formato de entrada é o seguinte:
- A primeira linha contém dois inteiros $c,n$.
- A segunda linha contém $p_0,p_1,\ldots,p_{n-1}$.
Se a resposta estiver correta, a biblioteca de interação escreve Correct! e Max queries used: Q, em que $Q$ é o número de consultas efetuadas nesse caso de teste; se a resposta estiver errada, escreve Wrong answer.. Quando uma consulta inválida é fornecida ou o limite de consultas é ultrapassado, o programa escreve uma mensagem de erro na saída de erro padrão e termina. Pode adicionar a opção -v para ver o número de consultas desse caso de teste.
Exemplos
Entrada 1
0 10
0 2 9 1 5 8 3 7 6 4Saída 1
Correct!
Max queries used: 15Nota
Por exemplo, ao chamar query(0,1,2), os três valores correspondentes são $0,2,9$, e o valor devolvido é $0+9=9$. O programa de referência utiliza $15$ consultas nesta instância. Se utilizar outra estratégia, esse número pode ser diferente.
Restrições
Para todos os dados de teste, $n\in\{10,100,10^5\}$ e $p$ é uma permutação de $0\sim n-1$. Cada caso de teste contém exatamente uma instância.
| Número da subtarefa | Pontuação | $n =$ | $Q_{\max} = $ | Propriedade especial |
|---|---|---|---|---|
| $1$ | $5$ | $10$ | $1000$ | Nenhuma |
| $2$ | $5$ | $100$ | $10000$ | Nenhuma |
| $3$ | $30$ | $10^5$ | $2\times10^6$ | $p_0=0$ |
| $4$ | $60$ | $10^5$ | $2\times10^6$ | Nenhuma |
No exemplo, $c=0$ e $n=10$, e o limite de consultas é $1000$.
Pontuação
Atenção:
- A biblioteca de interação não é adaptativa. A permutação de cada caso de teste é fixada antes de chamar o programa do participante e não muda em função das consultas.
- Não pode obter a permutação oculta lendo a entrada padrão ou por outros meios não permitidos. A implementação da biblioteca de interação utilizada na avaliação final pode ser diferente da biblioteca local.
Se, num caso de teste, mousse devolver uma resposta errada, os argumentos de query forem inválidos ou o número de consultas ultrapassar o $Q_{\max}$ dessa subtarefa, o multiplicador de pontuação desse caso de teste será $0$.
Nas subtarefas $1,2$, só receberá a pontuação total da subtarefa se todos os casos de teste estiverem corretos.
Para as subtarefas $3,4$, se o multiplicador de pontuação de qualquer caso de teste for $0$, a subtarefa recebe $0$ pontos. Caso contrário, seja $Q$ o maior número de consultas entre todos os casos de teste dessa subtarefa. O multiplicador de pontuação $f(Q)$ é determinado pela tabela seguinte:
| Número de consultas $Q_i$ | Multiplicador de pontuação $f_i$ |
|---|---|
| $99970$ | $100\%$ |
| $99975$ | $98\%$ |
| $99981$ | $95\%$ |
| $99988$ | $90\%$ |
| $99996$ | $84\%$ |
| $100000$ | $80\%$ |
| $100010$ | $74\%$ |
| $100026$ | $66\%$ |
| $100051$ | $58\%$ |
| $100093$ | $52\%$ |
| $150000$ | $32\%$ |
| $200000$ | $20\%$ |
| $1660964$ | $8\%$ |
| $2000000$ | $5\%$ |
Se $Q\le 99970$, então $f(Q)=100\%$. Se $Q$ estiver entre duas linhas consecutivas da tabela, $(Q_i,f_i)$ e $(Q_{i+1},f_{i+1})$, então:
$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$
A pontuação da subtarefa $3$ é $30f(Q)$, e a pontuação da subtarefa $4$ é $60f(Q)$. A pontuação final é arredondada a $3$ casas decimais.
Limite de tempo: $10\ \mathrm{s}$.
Limite de memória: $512\ \mathrm{MiB}$.