Anna e Bruno são mestres dos jogos de azar. Eles jogarão com D-taro, que será o crupiê.

Neste jogo, Anna e Bruno ficam em salas diferentes. Eles só podem comunicar entre si usando um dispositivo avariado. D-taro dá um inteiro a Anna. O objetivo de Anna e Bruno é transmitir esse inteiro de Anna para Bruno através do dispositivo.

No início do jogo, Anna declara um inteiro $m$ entre $1$ e $2\,000$, inclusive. Depois, jogam $Q$ rondas. A ronda $i$ ($1\le i\le Q$) decorre da seguinte forma.

1. D-taro dá um inteiro $A_i$ a Anna.
2. Anna introduz os vetores $s_i,t_i$ no dispositivo. Cada elemento dos vetores $s_i,t_i$ deve ser 0 ou 1. Os dois vetores devem ter o mesmo comprimento, entre $1$ e $m$, inclusive.
3. Seja $u_i$ um vetor obtido a partir de $s_i$ e $t_i$ por intercalação (ver abaixo). O dispositivo envia $u_i$ a Bruno.
4. Bruno envia um inteiro a D-taro. Se esse inteiro for igual a $A_i$, o inteiro que D-taro deu a Anna, Anna e Bruno ganham esta ronda.

Escreva programas que implementem as estratégias de Anna e Bruno de modo que ganhem todas as $Q$ rondas.

Intercalação

Dizemos que um vetor $Z$ é obtido a partir dos vetores $X$ e $Y$ por intercalação se for possível dividir os elementos de $Z$ em dois grupos que satisfaçam as duas condições seguintes.

• O vetor formado pelos elementos do primeiro grupo, mantendo a ordem, é igual ao vetor $X$.
• O vetor formado pelos elementos do segundo grupo, mantendo a ordem, é igual ao vetor $Y$.

Por exemplo, $Z=[1,1,1,0,0,0]$ é obtido a partir de $X=[1,1,0]$ e $Y=[1,0,0]$ por intercalação: o vetor formado pelo primeiro, segundo e quarto elementos de $Z$, nessa ordem, é $[1,1,0]$, e o vetor formado pelo terceiro, quinto e sexto elementos de $Z$, nessa ordem, é $[1,0,0]$.

Por outro lado, se $X=[1,1,0]$, $Y=[1,0,0]$ e $Z=[0,0,0,1,1,1]$, o vetor $Z$ não é obtido a partir de $X$ e $Y$ por intercalação.

Detalhes de implementação

É necessário submeter dois ficheiros.

O primeiro ficheiro é Anna.cpp. Deve implementar a estratégia de Anna e as funções seguintes. O programa deve incluir Anna.h através da diretiva de pré-processamento #include.

• int Declare()

  Esta função é chamada uma vez no início.

  • O valor devolvido é o inteiro $m$ declarado por Anna.
  • O inteiro $m$ deve estar entre $1$ e $2\,000$, inclusive. Se esta condição não for satisfeita, o programa recebe o veredicto Wrong Answer [1].

• std::pair<std::vector<int>, std::vector<int> > Anna(long long A)

  Após a chamada de Declare, esta função é chamada $Q$ vezes. A chamada de índice $i$ ($1\le i\le Q$) corresponde aos passos 1 e 2 da ronda $i$.

  • O parâmetro A é o inteiro $A_i$ dado por D-taro a Anna.
  • O valor devolvido é o par de vetores $s_i,t_i$ introduzidos por Anna no dispositivo.
  • Cada elemento dos vetores $s_i,t_i$ deve ser 0 ou 1. Caso contrário, o programa recebe o veredicto Wrong Answer [2].
  • Os comprimentos de ambos os vetores $s_i,t_i$ devem estar entre $1$ e $m$, inclusive. Caso contrário, o programa recebe o veredicto Wrong Answer [3].
  • Os vetores $s_i,t_i$ devem ter o mesmo comprimento. Caso contrário, o programa recebe o veredicto Wrong Answer [4].

O segundo ficheiro é Bruno.cpp. Deve implementar a estratégia de Bruno e a função seguinte. O programa deve incluir Bruno.h através da diretiva de pré-processamento #include.

• long long Bruno(std::vector<int> u)

  Esta função é chamada uma vez depois de Anna introduzir os vetores no dispositivo. No total, é chamada $Q$ vezes. A chamada de índice $i$ ($1\le i\le Q$) corresponde aos passos 3 e 4 da ronda $i$.

  • O parâmetro u é o vetor $u_i$ enviado pelo dispositivo a Bruno na ronda $i$.
  • O valor devolvido é o inteiro enviado por Bruno a D-taro.
  • O valor devolvido deve ser igual ao inteiro $A_i$ dado por D-taro a Anna. Caso contrário, o programa recebe o veredicto Wrong Answer [5].

Observações importantes

• O programa pode implementar outras funções para uso interno ou utilizar variáveis globais. Os ficheiros submetidos serão compilados com o avaliador, formando um único executável. Todas as variáveis globais e funções internas devem ser declaradas num espaço de nomes anónimo para evitar conflitos com outros ficheiros. Na avaliação, o programa será executado como dois processos, um de Anna e outro de Bruno. Estes processos não podem partilhar variáveis globais.
• O programa não deve utilizar a entrada padrão nem a saída padrão. Não deve comunicar com outros ficheiros por qualquer meio. No entanto, pode escrever informação de depuração na saída de erro padrão.

Compilação e execução de testes

Pode descarregar da página do concurso um arquivo que contém o avaliador de exemplo para testar o programa. O arquivo também contém um ficheiro de código-fonte de exemplo para o programa.

O avaliador de exemplo é o ficheiro grader.cpp. Para testar o programa, coloque grader.cpp, Anna.cpp, Bruno.cpp, Anna.h e Bruno.h no mesmo diretório e execute a seguinte linha de comando para compilar os programas.

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Se a compilação for bem-sucedida, será gerado o executável grader.

Note que o avaliador real difere do avaliador de exemplo. O avaliador de exemplo será executado como um único processo, lendo dados da entrada padrão e escrevendo os resultados na saída padrão.

Entrada do avaliador de exemplo

O avaliador de exemplo lê os seguintes dados da entrada padrão.

$$ \begin{array}{l} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{array} $$

Saída do avaliador de exemplo

O avaliador de exemplo escreve as seguintes informações na saída padrão (as aspas são usadas para maior clareza).

• Se o programa for considerado correto, escreve o valor $m$ devolvido por Declare no formato Accepted: 2000.
• Se o programa receber algum veredicto Wrong Answer, o avaliador de exemplo escreve o respetivo tipo no formato Wrong Answer [1].

Se o programa satisfizer as condições de vários tipos de Wrong Answer, o avaliador de exemplo reporta apenas um deles.

Quando o avaliador de exemplo é executado, a intercalação de cada ronda é calculada usando números pseudoaleatórios. Os resultados não mudam entre execuções. Para alterar a semente dos números pseudoaleatórios, execute o avaliador de exemplo da seguinte forma.

./grader 2022

O primeiro argumento deve ser um inteiro.

Restrições

• $1\le Q\le 1\,000$.
• $1\le A_i\le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1\le i\le Q$).

Subtarefas

1. (5 pontos) $A_i\le 2\,000$ ($1\le i\le Q$).
2. (5 pontos) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
3. (3 pontos) $A_i\le 10\,000\,000\ (=10^7)$ ($1\le i\le Q$).
4. (12 pontos) $A_i\le 100\,000\,000\ (=10^8)$ ($1\le i\le Q$).
5. (15 pontos) $A_i\le 100\,000\,000\,000\ (=10^{11})$ ($1\le i\le Q$).

6. (60 pontos) Sem restrições adicionais. Nesta subtarefa, a pontuação é calculada da seguinte forma.

   • Seja $m^*$ o máximo dos inteiros $m$ declarados por Anna em todos os casos de teste desta subtarefa.
   • A pontuação é dada pela tabela seguinte.

Exemplo de comunicação

Segue-se um exemplo de entrada para o avaliador de exemplo e as chamadas de funções correspondentes.

Entrada 1

2
42
2000

Chamadas de funções de exemplo

Neste exemplo, há $Q=2$ rondas. Na ronda $1$, D-taro dá a Anna o inteiro $A_1=42$. Na ronda $2$, D-taro dá a Anna o inteiro $A_2=2000$.

Esta entrada de exemplo satisfaz as restrições de todas as subtarefas.