Aidos a imaginé une énigme et a mis Temirulan au défi de la résoudre. Il a choisi une séquence $a$ de $n$ entiers non négatifs distincts numérotés de $1$ à $n$ : $a_1, a_2, \dots, a_n$.

Temirulan peut poser deux types de questions :

• ask — Révèle le nombre à la position $i$ de la séquence donnée.
• get_pairwise_xor — Pour la séquence donnée d'entiers distincts : $i_1, i_2, \dots, i_k$, obtient un ensemble de valeurs de $xor$ par paires pour les éléments de la séquence $a$ aux indices $i_1, i_2, \dots, i_k$, $\{a_{i_x} \oplus a_{i_y} \mid 1 \le x, y \le k\}$.

Par exemple, supposons qu'Aidos ait choisi la séquence $[1, 5, 6, 3]$. Alors pour la question ask(2), Aidos répondra avec le nombre 5 et pour la question get_pairwise_xor({3, 4}), Aidos répondra avec la séquence $[0, 0, 5, 5]$, car :

• $a_3 \oplus a_4 = 6 \oplus 3 = 5$
• $a_4 \oplus a_3 = 3 \oplus 6 = 5$
• $a_3 \oplus a_3 = 6 \oplus 6 = 0$
• $a_4 \oplus a_4 = 3 \oplus 3 = 0$.

Temirulan n'a pas réussi à résoudre l'énigme et votre tâche est de l'aider. Trouvez la séquence cachée en utilisant les questions décrites ci-dessus.

Entrée

VOS SOUMISSIONS NE DOIVENT PAS LIRE DEPUIS L'ENTRÉE STANDARD, ÉCRIRE VERS LA SORTIE STANDARD OU INTERAGIR AVEC TOUT AUTRE FICHIER.

Votre tâche est d'implémenter la fonction suivante : int[] guess(int n)

• $n$ : la longueur de la séquence cachée.
• La fonction est appelée exactement une fois pour chaque test.
• La fonction doit retourner la séquence cachée dans le même ordre.

Votre fonction peut appeler les fonctions suivantes :

1. int ask(int i)

   • $i$ : indice du nombre dans la séquence, $1 \le i \le n$.
   • La fonction retourne le $i$-ième nombre de la séquence cachée.

2. int[] get_pairwise_xor(int[] pos)

   • $pos$ : liste non vide d'indices de la séquence.
   • Tous les éléments dans $pos$ doivent être des entiers distincts.
   • Soit $k$ le nombre d'éléments dans $pos$. Alors $1 \le pos_i \le n$ pour chaque $1 \le i \le k$.
   • La fonction retourne une liste triée de $k^2$ éléments : un ensemble de valeurs $xor$ par paires, $\{a_{pos_x} \oplus a_{pos_y} \mid 1 \le x, y \le k\}$.

Vous pouvez appeler les deux fonctions au total pas plus de 200 fois pour chaque test. Si l'une des conditions ci-dessus est violée, votre programme recevra un verdict de Réponse Incorrecte (Wrong Answer). Sinon, votre programme recevra un verdict Accepté (Accepted) et votre score sera calculé en fonction du nombre total d'appels aux fonctions ask et get_pairwise_xor (Référez-vous à la section « Sous-tâches »).

Sous-tâches

• $2 \le n \le 100$
• $0 \le a_i \le 10^9$ pour chaque $1 \le i \le n$.

Dans cette tâche, le correcteur n'est PAS adaptatif. Cela signifie que la séquence $a$ est fixée au début de l'exécution du correcteur et ne dépend pas des appels de votre programme.

1. (6 points) $n \le 4$
2. (94 points) Aucune contrainte supplémentaire. Pour cette sous-tâche, votre score est calculé de la manière suivante. Soit $q$ le nombre total d'appels aux fonctions ask et get_pairwise_xor.
   • Si $q \le 15$, votre score est 94.
   • Si $15 < q \le 40$, votre score est $84 - 2(q - 16)$.
   • Si $40 < q \le 50$, votre score est 35.
   • Sinon, votre score est 0.

Notez que votre score pour chaque sous-tâche est le score minimum parmi tous les résultats sur les tests de la sous-tâche correspondante.

Remarque

L'opération $xor$ est le OU exclusif bit à bit.

Exemples

Entrée 1

4
1 5 6 3

Sortie 1

ask(2)

Remarque

Le correcteur appelle la fonction. Un exemple d'interaction est donné ci-dessous :

ask(2) retourne 5 get_pairwise_xor({1, 2, 3}) retourne {0, 0, 0, 3, 3, 4, 4, 7, 7} ask(3) retourne 6 get_pairwise_xor({4, 2}) retourne {0, 0, 6, 6} get_pairwise_xor({2}) retourne {0}

Le correcteur d'exemple lit l'entrée dans le format suivant :

• Ligne 1 : $n$
• Ligne 2 : $a_1, a_2, \dots, a_n$

VOUS POUVEZ TÉLÉCHARGER xoractive.zip dans le système qui contient des exemples pour les langages Java, C++11, FPC, Python 2.

Tous les exemples d'appel des fonctions se trouvent ci-dessus. Pour Python 2, vous devez implémenter la fonction def guess(n, interactor), où interactor est une instance de la classe testée. Les fonctions ask et get_pairwise_xor sont les méthodes de cette classe.

xoractive.zip contient des exemples de solutions pour chaque langage.

Pour les solutions en langage Java, le nom du fichier et de la classe doivent être nommés Xoractive.java et Xoractive respectivement.

Pour les solutions en langage Pascal, le fichier doit être nommé xoractive.pas.