In der Fabrik von JOI Co., Ltd. gibt es $N$ Tische, nummeriert von $0$ bis $N-1$, und $N-1$ Förderbänder, nummeriert von $0$ bis $N-2$. Förderband $i$ ($0 \le i \le N-2$) verbindet die Tische $A_i$ und $B_i$ und transportiert Produkte von einem dieser Tische zum anderen. Die Transportrichtung ist jedoch nicht sichtbar. Ignoriert man die Richtungen der Förderbänder, ist jedes Paar von Tischen über einige Förderbänder verbunden.

IOI-kun ist der Fabrikleiter. Da er die Transportrichtung jedes Förderbandes vergessen hat, wird er die folgende Abfolge von Operationen mehrmals ausführen.

1. Er wählt einige Förderbänder aus und kehrt deren Transportrichtungen um.
2. Er wählt einige Tische aus und legt auf jeden davon ein Produkt.

3. Für jeden Tisch, auf den ein Produkt gelegt wurde, geschieht gleichzeitig Folgendes:

   • Geht von ihm kein Förderband aus, das Produkte wegtransportiert, geschieht nichts.
   • Gehen von ihm solche Förderbänder aus, wird das Produkt über eines davon transportiert. Es bleibt am Zieltisch dieses Förderbandes liegen und bewegt sich nicht weiter.

4. IOI-kun prüft für jeden Tisch, ob darauf mindestens ein Produkt liegt. Liegen dort Produkte, nimmt er alle weg.

5. Er kehrt die Richtung jedes in Operation 1 umgekehrten Förderbandes erneut um und stellt so dessen ursprüngliche Richtung wieder her.

IOI-kun möchte die ursprüngliche Richtung jedes Förderbandes bestimmen, indem er diese Operationsfolge höchstens $30$ Mal ausführt.

Schreibe ein Programm, das anhand der Informationen darüber, welche Tische durch Förderbänder verbunden sind, IOI-kuns Strategie umsetzt, um die ursprüngliche Richtung jedes Förderbandes mit höchstens $30$ solchen Operationsfolgen zu bestimmen.

Implementierungsdetails

Du musst eine Datei abgeben.

Sie heißt conveyor.cpp und soll die folgende Funktion implementieren. Das Programm soll conveyor.h mit der Präprozessoranweisung #include einbinden.

In conveyor.cpp soll die folgende Funktion implementiert werden.

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

Diese Funktion wird für jeden Testfall nur einmal aufgerufen.

• Der Parameter N ist die Anzahl der Tische $N$.
• Die Parameter A und B sind Arrays der Länge $N-1$, die die durch Förderbänder verbundenen Tische beschreiben.

Dein Programm kann die folgende Funktion aufrufen.

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

Mit dieser Funktion führt IOI-kun die Operationen in der Fabrik aus.

• Der Parameter x ist ein Array der Länge $N-1$. Für $0 \le i \le N-2$ kehrt IOI-kun die Richtung von Förderband $i$ um, wenn x[i] = 1, und lässt sie unverändert, wenn x[i] = 0.
• Der Parameter y ist ein Array der Länge $N$. Für $0 \le j \le N-1$ legt IOI-kun ein Produkt auf Tisch $j$, wenn y[j] = 1, und keines, wenn y[j] = 0.
• Sei z der Rückgabewert der Funktion. Es ist ein Array der Länge $N$. Für $0 \le j \le N-1$ liegt auf Tisch $j$ mindestens ein Produkt, wenn z[j] = 1, und kein Produkt, wenn z[j] = 0.
• Das Array x muss die Länge $N-1$ haben. Andernfalls wird dein Programm mit Falsche Antwort (Wrong Answer [1]) bewertet.
• Jedes Element von x muss $0$ oder $1$ sein. Andernfalls wird dein Programm mit Falsche Antwort (Wrong Answer [2]) bewertet.
• Das Array y muss die Länge $N$ haben. Andernfalls wird dein Programm mit Falsche Antwort (Wrong Answer [3]) bewertet.
• Jedes Element von y muss $0$ oder $1$ sein. Andernfalls wird dein Programm mit Falsche Antwort (Wrong Answer [4]) bewertet.
• Query darf höchstens $30$ Mal aufgerufen werden. Bei mehr als $30$ Aufrufen wird dein Programm mit Falsche Antwort (Wrong Answer [5]) bewertet.

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

Mit dieser Funktion meldet IOI-kun die ursprüngliche Richtung jedes Förderbandes.

• Der Parameter a ist ein Array der Länge $N-1$. Für $0 \le i \le N-2$ transportiert Förderband $i$ Produkte von $A_i$ nach $B_i$, wenn a[i] = 0, und von $B_i$ nach $A_i$, wenn a[i] = 1.
• Das Array a muss die Länge $N-1$ haben. Andernfalls wird dein Programm mit Falsche Antwort (Wrong Answer [6]) bewertet.
• Jedes Element von a muss $0$ oder $1$ sein. Andernfalls wird dein Programm mit Falsche Antwort (Wrong Answer [7]) bewertet.
• Meldet IOI-kun die Richtung eines Förderbandes falsch, wird dein Programm mit Falsche Antwort (Wrong Answer [8]) bewertet.
• Answer muss genau einmal aufgerufen werden. Bei mehr als einem Aufruf wird dein Programm mit Falsche Antwort (Wrong Answer [9]) bewertet. Wurde Answer beim Beenden von Solve nicht aufgerufen, wird dein Programm mit Falsche Antwort (Wrong Answer [10]) bewertet.

Wichtige Hinweise

• Dein Programm darf weitere Funktionen für den internen Gebrauch implementieren oder globale Variablen verwenden.
• Dein Programm darf weder die Standardeingabe noch die Standardausgabe verwenden und auf keine Weise mit anderen Dateien kommunizieren. Es darf jedoch Informationen zur Fehlersuche auf die Standardfehlerausgabe schreiben.

Kompilieren und Testen

Auf der Wettbewerbswebseite kannst du ein Archiv mit einem Beispielgrader zum Testen deines Programms herunterladen. Es enthält außerdem eine Beispieldatei für den Quellcode deines Programms.

Der Beispielgrader ist die Datei grader.cpp. Lege zum Testen grader.cpp, conveyor.cpp und conveyor.h im selben Verzeichnis ab und führe den folgenden Befehl aus, um die Programme zu kompilieren. Alternativ kannst du compile.sh aus dem Archiv ausführen.

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

Nach erfolgreicher Kompilierung wird die ausführbare Datei grader erzeugt.

Beachte, dass der tatsächliche Grader vom Beispielgrader abweicht. Der Beispielgrader wird als einzelner Prozess ausgeführt, der Daten von der Standardeingabe liest und Ergebnisse auf die Standardausgabe schreibt.

Eingabe des Beispielgraders

Der Beispielgrader liest die folgenden Daten von der Standardeingabe.

$$ \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} $$

Für $0 \le i \le N-2$ gilt $C_i=0$, wenn Förderband $i$ Produkte von Tisch $A_i$ nach Tisch $B_i$ transportiert. Andernfalls gilt $C_i=1$.

Ausgabe des Beispielgraders

Der Beispielgrader schreibt die folgenden Informationen auf die Standardausgabe (Anführungszeichen dienen nur der Verdeutlichung).

• Wird dein Programm als korrekt bewertet, gibt er die Anzahl der Aufrufe von Query in der Form Accepted: 22 aus.
• Wird dein Programm mit irgendeiner Art von Falsche Antwort bewertet, gibt der Beispielgrader deren Typ in der Form Wrong Answer [4] aus.

Erfüllt dein Programm die Bedingungen mehrerer Arten von Falsche Antwort, meldet der Beispielgrader nur eine davon.

Im Beispielgrader wird unter den von einem Tisch mit einem aufgelegten Produkt ausgehenden Förderbändern das transportierende Förderband gleichverteilt zufällig gewählt. Dazu dienen Pseudozufallszahlen, deren Ergebnisse zwischen verschiedenen Ausführungen gleich bleiben. Um den Startwert des Pseudozufallszahlengenerators zu ändern, starte den Beispielgrader wie folgt mit einem ersten ganzzahligen Argument.

./grader 2023

Hinweise zur Bewertung

Für einige Testfälle ist der tatsächliche Grader adaptiv. Das bedeutet, dass er anfangs keine feste Antwort hat und abhängig von den bisherigen Query-Aufrufen antwortet. Es ist garantiert, dass mindestens eine Antwort existiert, die mit sämtlichen Antworten des Graders vereinbar ist.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $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$).
• Ignoriert man die Richtungen der Förderbänder, ist jedes Paar von Tischen über einige Förderbänder verbunden.

Teilaufgaben

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

Beispiele

Hier folgen eine Beispieleingabe für den Beispielgrader und die zugehörigen Funktionsaufrufe.

Eingabe 1

3
0 2
2 1
1 0

Beispielhafte Funktionsaufrufe

Hinweis

Beim ersten Query-Aufruf ist neben [1, 0, 0] auch [0, 1, 0] als Rückgabewert möglich.

Beim zweiten Query-Aufruf wird das Produkt auf Tisch $0$ über Förderband $0$ zu Tisch $2$ transportiert und bleibt dort liegen. Beachte, dass es anschließend nicht über Förderband $1$ zu Tisch $1$ transportiert wird.

Beachte, dass diese Beispieleingabe die Beschränkungen keiner Teilaufgabe erfüllt.

Unter den von der Wettbewerbswebseite herunterladbaren Dateien erfüllt sample-02.txt die Beschränkungen von Teilaufgabe 1 und sample-03.txt diejenigen von Teilaufgabe 2.