Anna et Bruno sont des maîtres du jeu. Ils vont participer à un jeu dont D-taro est le croupier.

Dans ce jeu, Anna et Bruno restent dans des pièces différentes. Ils ne peuvent communiquer entre eux qu'à l'aide d'un appareil défectueux. D-taro donne un entier à Anna. Leur objectif est de transmettre cet entier d'Anna à Bruno à l'aide de l'appareil.

Au début du jeu, Anna annonce d'abord un entier $m$ compris entre $1$ et $2\,000$, bornes incluses. Ils jouent ensuite $Q$ manches. La manche $i$ ($1\le i\le Q$) se déroule ainsi :

1. D-taro donne un entier $A_i$ à Anna.
2. Anna saisit deux tableaux $s_i,t_i$ dans l'appareil. Chaque élément de ces tableaux doit être $0$ ou $1$. Les tableaux doivent avoir la même longueur, comprise entre $1$ et $m$, bornes incluses.
3. Soit $u_i$ un tableau obtenu par entrelacement des tableaux $s_i$ et $t_i$ (voir ci-dessous). L'appareil transmet alors $u_i$ à Bruno.
4. Bruno transmet un entier à D-taro. Si cet entier est égal à l'entier $A_i$ donné par D-taro à Anna, Anna et Bruno remportent cette manche.

Écrivez des programmes mettant en œuvre les stratégies d'Anna et de Bruno afin qu'ils remportent les $Q$ manches.

Entrelacement

On dit qu'un tableau $Z$ est obtenu par entrelacement des tableaux $X$ et $Y$ si l'on peut répartir les éléments de $Z$ en deux groupes de sorte que les deux conditions suivantes soient respectées.

• Le tableau formé des éléments du premier groupe, dans leur ordre d'origine, est égal au tableau $X$.
• Le tableau formé des éléments du second groupe, dans leur ordre d'origine, est égal au tableau $Y$.

Par exemple, le tableau $Z=[1,1,1,0,0,0]$ est obtenu par entrelacement de $X=[1,1,0]$ et de $Y=[1,0,0]$, car le tableau formé des premier, deuxième et quatrième éléments de $Z$, dans cet ordre, est $[1,1,0]$, et celui formé des troisième, cinquième et sixième éléments, dans cet ordre, est $[1,0,0]$.

En revanche, si $X=[1,1,0]$, $Y=[1,0,0]$ et $Z=[0,0,0,1,1,1]$, le tableau $Z$ n'est pas obtenu par entrelacement de $X$ et de $Y$.

Détails d'implémentation

Vous devez soumettre deux fichiers.

Le premier fichier est Anna.cpp. Il doit mettre en œuvre la stratégie d'Anna et implémenter les fonctions suivantes. Le programme doit inclure Anna.h au moyen de la directive de prétraitement #include.

• int Declare()

  Cette fonction est appelée une seule fois, au début.

  • La valeur renvoyée est l'entier $m$ annoncé par Anna.
  • L'entier $m$ doit être compris entre $1$ et $2\,000$, bornes incluses. Sinon, votre programme reçoit le verdict Wrong Answer [1].

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

  Après l'appel de Declare, cette fonction est appelée $Q$ fois. Le $i$-ème appel ($1\le i\le Q$) correspond aux étapes 1 et 2 de la manche $i$.

  • Le paramètre A est l'entier $A_i$ donné par D-taro à Anna.
  • La valeur renvoyée est la paire des deux tableaux $s_i,t_i$ saisis par Anna dans l'appareil.
  • Chaque élément des tableaux $s_i,t_i$ doit être $0$ ou $1$. Sinon, votre programme reçoit le verdict Wrong Answer [2].
  • Les longueurs des deux tableaux $s_i,t_i$ doivent être comprises entre $1$ et $m$, bornes incluses. Sinon, votre programme reçoit le verdict Wrong Answer [3].
  • Les tableaux $s_i,t_i$ doivent avoir la même longueur. Sinon, votre programme reçoit le verdict Wrong Answer [4].

Le second fichier est Bruno.cpp. Il doit mettre en œuvre la stratégie de Bruno et implémenter la fonction suivante. Le programme doit inclure Bruno.h au moyen de la directive de prétraitement #include.

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

  Après qu'Anna a saisi les tableaux dans l'appareil, cette fonction est appelée une fois. Au total, elle est appelée $Q$ fois. Le $i$-ème appel ($1\le i\le Q$) correspond aux étapes 3 et 4 de la manche $i$.

  • Le paramètre u est le tableau $u_i$ transmis par l'appareil à Bruno pour la manche $i$.
  • La valeur renvoyée est l'entier transmis par Bruno à D-taro.
  • La valeur renvoyée doit être égale à l'entier $A_i$ donné par D-taro à Anna. Sinon, votre programme reçoit le verdict Wrong Answer [5].

Remarques importantes

• Votre programme peut implémenter d'autres fonctions à usage interne ou utiliser des variables globales. Les fichiers soumis seront compilés avec l'évaluateur pour former un seul exécutable. Toutes les variables globales et fonctions internes doivent être déclarées dans un espace de noms anonyme afin d'éviter les conflits avec les autres fichiers. Lors de l'évaluation, le programme sera exécuté sous la forme de deux processus, l'un pour Anna et l'autre pour Bruno. Ces deux processus ne peuvent pas partager de variables globales.
• Votre programme ne doit utiliser ni l'entrée standard ni la sortie standard. Il ne doit communiquer avec d'autres fichiers par aucun moyen. Il peut toutefois écrire des informations de débogage sur la sortie d'erreur standard.

Compilation et exécution de test

Vous pouvez télécharger depuis la page du concours une archive contenant l'évaluateur d'exemple pour tester votre programme. L'archive contient également un exemple de fichier source de votre programme.

L'évaluateur d'exemple est le fichier grader.cpp. Pour tester votre programme, placez grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h dans le même répertoire et exécutez la commande suivante pour compiler vos programmes.

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

Si la compilation réussit, l'exécutable grader est généré.

Attention : l'évaluateur réel est différent de celui d'exemple. L'évaluateur d'exemple s'exécute en un seul processus, qui lit les données sur l'entrée standard et écrit les résultats sur la sortie standard.

Entrée de l'évaluateur d'exemple

L'évaluateur d'exemple lit les données suivantes sur l'entrée standard.

$Q$

$A_1$

$A_2$

$\vdots$

$A_Q$

Sortie de l'évaluateur d'exemple

L'évaluateur d'exemple écrit les informations suivantes sur la sortie standard (les guillemets servent à délimiter le texte).

• Si votre programme est jugé correct, il écrit la valeur $m$ renvoyée par Declare sous la forme Accepted: 2000.
• Si votre programme reçoit un verdict Wrong Answer, l'évaluateur d'exemple écrit son type sous la forme Wrong Answer [1].

Si votre programme remplit les conditions de plusieurs types de Wrong Answer, l'évaluateur d'exemple n'en signale qu'un seul.

Lors de l'exécution de l'évaluateur d'exemple, l'entrelacement de chaque manche est calculé à l'aide de nombres pseudo-aléatoires. Les résultats restent identiques d'une exécution à l'autre. Pour changer la graine du générateur pseudo-aléatoire, exécutez l'évaluateur d'exemple de la manière suivante.

./grader 2022

Le premier argument doit être un entier.

Contraintes

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

Sous-tâches

1. (5 points) $A_i\le2\,000$ ($1\le i\le Q$).
2. (5 points) $A_i\le4\,000\,000$ ($1\le i\le Q$).
3. (3 points) $A_i\le10\,000\,000$ ($=10^7$) ($1\le i\le Q$).
4. (12 points) $A_i\le100\,000\,000$ ($=10^8$) ($1\le i\le Q$).
5. (15 points) $A_i\le100\,000\,000\,000$ ($=10^{11}$) ($1\le i\le Q$).

6. (60 points) Aucune contrainte supplémentaire. Pour cette sous-tâche, votre score est calculé comme suit.

   • Soit $m^*$ le maximum des entiers $m$ annoncés par Anna sur tous les cas de test de cette sous-tâche.
   • Votre score est le suivant.

Exemple de communication

Voici un exemple d'entrée pour l'évaluateur d'exemple et les appels de fonctions correspondants.

Exemples

Entrée 1

2
42
2000

Remarque

Appels de fonctions de l'exemple :

Dans cet exemple, il y a $Q$ ($=2$) manches. Lors de la manche 1, D-taro donne l'entier $A_1$ ($=42$) à Anna. Lors de la manche 2, D-taro donne l'entier $A_2$ ($=2000$) à Anna.

Cet exemple respecte les contraintes de toutes les sous-tâches.