Grafo das somas
Este problema é interativo. Se você nunca tiver visto um problema assim antes, cheque o guia de problemas interativos.
Existe uma permutação¹ escondida $$p$$ de tamanho $$n$$ e um grafo não-direcionado com $$n$$ vértices e, inicialmente, nenhuma aresta.
Dois tipos de operação podem ser feitas nesse grafo:
- Escolha um $$x$$ inteiro tal que $$2 \leq x \leq 2n$$. Para todo o par de vértices $$(i, j)$$ em que $$i + j = x$$, será adicionada uma aresta.
- Pergunte para o par $$(i, j)$$, $$1 \leq i, j \leq n$$, qual é o menor caminho em arestas entre os vértices $$p_i$$ e $$p_j$$. Se não houver nenhum caminho entre $$p_i$$ e $$p_j$$ a resposta será $$-1$$, caso contrário a resposta será a menor distância entre $$p_i$$ e $$p_j$$
Usando no máximo $$2n$$ operações (de ambos os tipos) descubra duas possíveis permutações $$p$$, a sua resposta será considerada correta se ao menos uma das suas duas respostas for a permutação certa. É permitido responder duas permutações iguais.
1 – Uma permutação de tamanho $$n$$ é um vetor de tamanho $$n$$ que contém os números de $$1$$ a $$n$$ em uma ordem arbitrária. Por exemplo, os vetores $$[1, 2, 3, 4]$$ e $$[5, 3, 1, 2, 4]$$ são permutações (de tamanho $$4$$ e $$5$$, respectivamente) porém os vetores $$[1, 2, 2]$$ e $$[2, 3, 4, 5]$$ não são permutações.
Entrada
A primeira linha contém um inteiro $$t$$ ($$1 \leq t \leq 100$$) que indica a quantidade de casos de teste.
A primeira linha de cada caso de teste apresenta um inteiro $$n$$ ($$ 2 \leq n \leq 10^3$$), o tamanho da permutação e quantidade de vérices do grafo.
É garantido que a soma dos $$n$$ de todos os casos de teste não excede $$10^3$$
Interação
A interação para cada caso começa ao ler o inteiro $$n$$.
Depois, faça no máximo $$2n$$ operações:
- Para fazer uma operação do tipo 1, imprima “+ $$x$$” (sem as aspas). Então leia um inteiro $$1$$ ou $$-2$$. Se o inteiro lido for $$1$$, a sua operação foi válida, caso contrário seu código deve terminar a execução imediatamente para receber o veredito de Resposta Errada.
- Para fazer uma operação de tipo 2, imprima “? $$i$$ $$j$$” (também sem as aspas). Em seguida, leia a resposta da operação. Caso a resposta lida tenha $$-2$$, o seu código fez uma operação inválida ou ultrapassou o limite de operações e, portanto, deve a execução deve cessar de imediato para receber Resposta Errada.
Para responder quais são as permutações, imprima “! $$p_{1,1}$$ $$p_{1,2}$$ … $$p_{1,n}$$ $$p_{2,1}$$ $$p_{2,2}$$… $$p_{2,n}$$” (de novo, sem as aspas), os dois vetores imprimidos devem ser permutações, mesmo que a primeira permutação esteja correta. Seu código deve então ler um inteiro $$1$$ ou $$-2$$, se o inteiro for $$-2$$, a resposta estava errada e o seu código deve retornar para receber o veredito Resposta Errada. Senão, a resposta estava correta e seu código deve seguir para o próximo caso de teste. Responder as permutações não conta como uma operação.
Exemplo
