Dans l'usine de JOI Co., Ltd., il y a $N$ tables, numérotées de $0$ à $N-1$, et $N-1$ convoyeurs à bande, numérotés de $0$ à $N-2$. Le convoyeur $i$ ($0\le i\le N-2$) relie les tables $A_i$ et $B_i$ et transporte les produits de l'une vers l'autre. Cependant, son sens de transport n'est pas visible. En ignorant le sens des convoyeurs, toute paire de tables est reliée par une suite de convoyeurs.

IOI-kun dirige l'usine. Ayant oublié le sens de chaque convoyeur, il effectuera plusieurs fois la séquence d'opérations suivante.

1. Il choisit un ensemble de convoyeurs et inverse leur sens de transport.
2. Il choisit un ensemble de tables et dépose un produit sur chacune.

3. Pour chaque table sur laquelle un produit a été déposé, l'une des situations suivantes se produit simultanément.

   • Si aucun convoyeur ne transporte de produits depuis cette table, rien ne se passe.
   • Sinon, le produit emprunte l'un des convoyeurs qui partent de cette table. Il s'arrête à la table d'arrivée de ce convoyeur et ne se déplace plus.

4. IOI-kun vérifie, pour chaque table, s'il s'y trouve au moins un produit. Si oui, il les retire tous.

5. Pour chaque convoyeur inversé à l'étape 1, IOI-kun rétablit son sens initial.

IOI-kun veut déterminer le sens initial de chaque convoyeur en effectuant cette séquence au plus $30$ fois.

Écrivez un programme qui, connaissant les tables reliées par les convoyeurs, met en œuvre la stratégie d'IOI-kun pour déterminer le sens initial de chaque convoyeur en effectuant la séquence au plus $30$ fois.

Détails d'implémentation

Vous devez soumettre un fichier.

Ce fichier, conveyor.cpp, doit implémenter la fonction suivante. Le programme doit inclure conveyor.h à l'aide de la directive de prétraitement #include.

Dans conveyor.cpp, implémentez la fonction suivante.

• void Solve(int N, std::vector<int> A, std::vector<int> B)

  Cette fonction est appelée une seule fois par test.

  • Le paramètre N est le nombre de tables $N$.
  • Les paramètres A, B sont des tableaux de longueur $N-1$ décrivant les tables reliées par les convoyeurs.

Votre programme peut appeler les fonctions suivantes.

• std::vector<int> Query(std::vector<int> x, std::vector<int> y)

  Cette fonction permet à IOI-kun d'effectuer les opérations dans l'usine.

  • Le paramètre x est un tableau de longueur $N-1$. Pour $0\le i\le N-2$, IOI-kun inverse le sens du convoyeur $i$ si x[i] = 1, et ne l'inverse pas si x[i] = 0.
  • Le paramètre y est un tableau de longueur $N$. Pour $0\le j\le N-1$, IOI-kun dépose un produit sur la table $j$ si y[j] = 1, et n'en dépose pas si y[j] = 0.
  • Soit z la valeur renvoyée, un tableau de longueur $N$. Pour $0\le j\le N-1$, la table $j$ contient au moins un produit si z[j] = 1, et aucun si z[j] = 0.
  • La longueur de x doit être $N-1$. Sinon, votre programme reçoit le verdict Wrong Answer [1].
  • Chaque élément de x doit être 0 ou 1. Sinon, votre programme reçoit le verdict Wrong Answer [2].
  • La longueur de y doit être $N$. Sinon, votre programme reçoit le verdict Wrong Answer [3].
  • Chaque élément de y doit être 0 ou 1. Sinon, votre programme reçoit le verdict Wrong Answer [4].
  • Query ne doit pas être appelée plus de $30$ fois. Sinon, votre programme reçoit le verdict Wrong Answer [5].

• void Answer(std::vector<int> a)

  Cette fonction permet à IOI-kun d'indiquer le sens initial de chaque convoyeur.

  • Le paramètre a est un tableau de longueur $N-1$. Pour $0\le i\le N-2$, le convoyeur $i$ transporte les produits de $A_i$ vers $B_i$ si a[i] = 0, et de $B_i$ vers $A_i$ si a[i] = 1.
  • La longueur de a doit être $N-1$. Sinon, votre programme reçoit le verdict Wrong Answer [6].
  • Chaque élément de a doit être 0 ou 1. Sinon, votre programme reçoit le verdict Wrong Answer [7].
  • Si IOI-kun indique un sens incorrect pour un convoyeur, votre programme reçoit le verdict Wrong Answer [8].
  • Answer doit être appelée exactement une fois. Si elle est appelée plusieurs fois, votre programme reçoit le verdict Wrong Answer [9]. Si Solve se termine sans appel à Answer, votre programme reçoit le verdict Wrong Answer [10].

Avis importants

• Votre programme peut implémenter d'autres fonctions internes ou utiliser des 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 tests

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

L'évaluateur d'exemple se trouve dans grader.cpp. Pour tester votre programme, placez grader.cpp, conveyor.cpp, conveyor.h dans le même répertoire et exécutez la commande suivante pour compiler. Vous pouvez aussi exécuter le script compile.sh fourni dans l'archive.

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

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

L'évaluateur réel est différent de celui d'exemple. L'évaluateur d'exemple s'exécute en un seul processus, lit 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.

$$ \begin{array}{l} N\\ A_0\ A_1\ \cdots\ A_{N-2}\\ B_0\ B_1\ \cdots\ B_{N-2}\\ C_0\ C_1\ \cdots\ C_{N-2} \end{array} $$

Pour $0\le i\le N-2$, on a $C_i=0$ si le convoyeur $i$ transporte les produits de la table $A_i$ vers la table $B_i$. Sinon, $C_i=1$.

Sortie de l'évaluateur d'exemple

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

• Si votre programme est jugé correct, il indique le nombre d'appels à Query, sous la forme Accepted: 22.
• Si votre programme reçoit un verdict Wrong Answer, il en indique le type, sous la forme Wrong Answer [4].

Si plusieurs types de Wrong Answer s'appliquent, l'évaluateur d'exemple n'en indique qu'un.

Dans l'évaluateur d'exemple, parmi les convoyeurs partant d'une table où un produit a été déposé, celui qui transporte le produit est choisi uniformément au hasard à l'aide de nombres pseudo-aléatoires dont les résultats ne changent pas entre les exécutions. Pour changer la graine, lancez l'évaluateur d'exemple avec un premier argument entier, comme suit.

./grader 2023

Remarques sur l'évaluation

Pour certains tests, l'évaluateur réel est adaptatif : il n'a pas de réponse fixée au début et répond en fonction des appels précédents à Query. Il est garanti qu'au moins une réponse est compatible avec toutes les réponses de l'évaluateur.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $0\le A_i\le N-1$ ($0\le i\le N-2$).
• $0\le B_i\le N-1$ ($0\le i\le N-2$).
• En ignorant le sens des convoyeurs, toute paire de tables est reliée par une suite de convoyeurs.

Sous-tâches

1. (1 point) $N=2$.
2. (14 points) $N=30$.
3. (10 points) $N=100\,000$, $A_i=i$ ($0\le i\le N-2$), $B_i=i+1$ ($0\le i\le N-2$).
4. (75 points) $N=100\,000$.

Exemple de communication

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

Entrée 1

3
0 2
2 1
1 0

Exemples d'appels de fonctions

Pour le premier appel à Query, [0, 1, 0] est une autre valeur de retour possible, en plus de [1, 0, 0].

Pour le deuxième appel à Query, le produit de la table $0$ est transporté jusqu'à la table $2$ par le convoyeur $0$ et s'y arrête. Ce produit ne sera pas transporté ensuite jusqu'à la table $1$ par le convoyeur $1$.

Cette entrée d'exemple ne satisfait les contraintes d'aucune sous-tâche.

Parmi les fichiers disponibles sur la page du concours, sample-02.txt satisfait les contraintes de la sous-tâche 1, et sample-03.txt celles de la sous-tâche 2.