Anna und Bruno sind Meister des Glücksspiels. Sie werden mit D-taro, dem Spielleiter, ein Spiel spielen.

In diesem Spiel befinden sich Anna und Bruno in verschiedenen Räumen. Sie können ausschließlich über ein defektes Gerät miteinander kommunizieren. D-taro gibt Anna eine ganze Zahl. Das Ziel von Anna und Bruno ist es, diese Zahl mithilfe des Geräts von Anna an Bruno zu übermitteln.

Zu Beginn des Spiels gibt Anna eine ganze Zahl $m$ zwischen $1$ und $2\,000$ einschließlich an. Anschließend spielen sie $Q$ Runden. Runde $i$ ($1 \le i \le Q$) läuft wie folgt ab.

1. D-taro gibt Anna eine ganze Zahl $A_i$.
2. Anna gibt die Arrays $s_i,t_i$ in das Gerät ein. Jedes Element dieser Arrays muss $0$ oder $1$ sein. Die Arrays müssen dieselbe Länge haben, und diese Länge muss zwischen $1$ und $m$ einschließlich liegen.
3. Sei $u_i$ ein Array, das durch ein Riffelmischen (siehe unten) der Arrays $s_i$ und $t_i$ entsteht. Das Gerät sendet $u_i$ an Bruno.
4. Bruno sendet eine ganze Zahl an D-taro. Stimmt diese Zahl mit der Zahl $A_i$ überein, die D-taro Anna gegeben hat, gewinnen Anna und Bruno diese Runde.

Schreibe Programme, die die Strategien von Anna und Bruno so implementieren, dass sie alle $Q$ Runden gewinnen.

Riffelmischen

Wir sagen, dass ein Array $Z$ durch Riffelmischen aus den Arrays $X$ und $Y$ entsteht, wenn sich die Elemente von $Z$ in zwei Gruppen aufteilen lassen, sodass die folgenden beiden Bedingungen erfüllt sind.

• Das Array aus den Elementen der ersten Gruppe in ihrer ursprünglichen Reihenfolge ist gleich $X$.
• Das Array aus den Elementen der zweiten Gruppe in ihrer ursprünglichen Reihenfolge ist gleich $Y$.

Zum Beispiel entsteht $Z=[1,1,1,0,0,0]$ durch Riffelmischen aus $X=[1,1,0]$ und $Y=[1,0,0]$: Das erste, zweite und vierte Element von $Z$ bilden in dieser Reihenfolge das Array $[1,1,0]$, und das dritte, fünfte und sechste Element bilden in dieser Reihenfolge das Array $[1,0,0]$.

Wenn hingegen $X=[1,1,0]$, $Y=[1,0,0]$ und $Z=[0,0,0,1,1,1]$ sind, entsteht $Z$ nicht durch Riffelmischen aus $X$ und $Y$.

Implementierungsdetails

Du musst zwei Dateien einreichen.

Die erste Datei ist Anna.cpp. Sie soll Annas Strategie und die folgenden Funktionen implementieren. Das Programm soll Anna.h mit der Präprozessoranweisung #include einbinden.

• int Declare()

  Diese Funktion wird zu Beginn einmal aufgerufen.

  • Der Rückgabewert ist die von Anna angegebene ganze Zahl $m$.
  • Die Zahl $m$ muss zwischen $1$ und $2\,000$ einschließlich liegen. Andernfalls wird dein Programm mit Wrong Answer [1] bewertet.

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

  Nach dem Aufruf von Declare wird diese Funktion $Q$-mal aufgerufen. Der $i$-te Aufruf ($1 \le i \le Q$) entspricht Schritt 1 und Schritt 2 der Runde $i$.

  • Der Parameter A ist die ganze Zahl $A_i$, die D-taro Anna gibt.
  • Der Rückgabewert ist das Paar der beiden Arrays $s_i,t_i$, die Anna in das Gerät eingibt.
  • Jedes Element der Arrays $s_i,t_i$ muss $0$ oder $1$ sein. Andernfalls wird dein Programm mit Wrong Answer [2] bewertet.
  • Die Längen beider Arrays $s_i,t_i$ müssen zwischen $1$ und $m$ einschließlich liegen. Andernfalls wird dein Programm mit Wrong Answer [3] bewertet.
  • Die Arrays $s_i,t_i$ müssen dieselbe Länge haben. Andernfalls wird dein Programm mit Wrong Answer [4] bewertet.

Die zweite Datei ist Bruno.cpp. Sie soll Brunos Strategie und die folgende Funktion implementieren. Das Programm soll Bruno.h mit der Präprozessoranweisung #include einbinden.

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

  Nachdem Anna die Arrays in das Gerät eingegeben hat, wird diese Funktion einmal aufgerufen. Insgesamt wird sie $Q$-mal aufgerufen. Der $i$-te Aufruf ($1 \le i \le Q$) entspricht Schritt 3 und Schritt 4 der Runde $i$.

  • Der Parameter u ist das Array $u_i$, das das Gerät in Runde $i$ an Bruno sendet.
  • Der Rückgabewert ist die ganze Zahl, die Bruno an D-taro sendet.
  • Der Rückgabewert muss gleich der ganzen Zahl $A_i$ sein, die D-taro Anna gegeben hat. Andernfalls wird dein Programm mit Wrong Answer [5] bewertet.

Wichtige Hinweise

• Dein Programm darf weitere Funktionen für den internen Gebrauch implementieren oder globale Variablen verwenden. Die eingereichten Dateien werden zusammen mit dem Grader zu einer einzigen ausführbaren Datei kompiliert. Alle globalen Variablen und internen Funktionen sollen in einem unbenannten Namensraum deklariert werden, um Konflikte mit anderen Dateien zu vermeiden. Bei der Bewertung läuft das Programm in zwei Prozessen, einem für Anna und einem für Bruno. Annas und Brunos Prozesse können keine globalen Variablen gemeinsam nutzen.
• Dein Programm darf weder die Standardeingabe noch die Standardausgabe verwenden. Es darf auf keine Weise mit anderen Dateien kommunizieren. Es darf jedoch Informationen zur Fehlersuche auf die Standardfehlerausgabe schreiben.

Kompilierung und Testlauf

Von der Wettbewerbswebseite kannst du ein Archiv herunterladen, das einen Beispiel-Grader zum Testen deines Programms enthält. Das Archiv enthält auch eine Beispiel-Quelldatei deines Programms.

Der Beispiel-Grader ist die Datei grader.cpp. Lege zum Testen grader.cpp,Anna.cpp,Bruno.cpp,Anna.h,Bruno.h in dasselbe Verzeichnis und führe den folgenden Befehl aus, um deine Programme zu kompilieren.

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

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

Beachte, dass sich der tatsächliche Grader vom Beispiel-Grader unterscheidet. Der Beispiel-Grader läuft als einzelner Prozess, der Eingabedaten von der Standardeingabe liest und Ergebnisse auf die Standardausgabe schreibt.

Eingabe für den Beispiel-Grader

Der Beispiel-Grader liest die folgenden Daten von der Standardeingabe.

$Q$

$A_1$

$A_2$

$\vdots$

$A_Q$

Ausgabe des Beispiel-Graders

Der Beispiel-Grader schreibt die folgenden Informationen auf die Standardausgabe (Anführungszeichen dienen der Verdeutlichung).

• Wird dein Programm als korrekt bewertet, gibt er den Rückgabewert $m$ der Funktion Declare in der Form Accepted: 2000 aus.
• Wird dein Programm mit einer der Bewertungen Wrong Answer bewertet, gibt der Beispiel-Grader deren Typ in der Form Wrong Answer [1] aus.

Erfüllt dein Programm die Bedingungen mehrerer Arten von Wrong Answer, meldet der Beispiel-Grader nur eine davon.

Beim Ausführen des Beispiel-Graders wird das Riffelmischen jeder Runde mithilfe von Pseudozufallszahlen berechnet. Die Ergebnisse ändern sich zwischen Ausführungen nicht. Um den Startwert der Pseudozufallszahlen zu ändern, führe den Beispiel-Grader wie folgt aus.

./grader 2022

Das erste Argument muss eine ganze Zahl sein.

Beschränkungen

• $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$).

Teilaufgaben

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

6. (60 Punkte) Keine zusätzlichen Beschränkungen. Für diese Teilaufgabe wird deine Punktzahl wie folgt berechnet.

   • Sei $m^*$ das Maximum der von Anna angegebenen ganzen Zahlen $m$ über alle Testfälle dieser Teilaufgabe.
   • Deine Punktzahl ist wie folgt.

Beispiele

Hier folgen eine Beispieleingabe für den Beispiel-Grader und die zugehörigen Funktionsaufrufe.

Eingabe 1

2
42
2000

Beispiel-Funktionsaufrufe

Hinweis

In dieser Beispieleingabe gibt es $Q\ (=2)$ Runden. In Runde 1 gibt D-taro Anna die ganze Zahl $A_1\ (=42)$. In Runde 2 gibt D-taro Anna die ganze Zahl $A_2\ (=2000)$.

Diese Beispieleingabe erfüllt die Beschränkungen aller Teilaufgaben.