Nach mehreren hundert Jahren wurde die Stadt JOI zu einer Ruinenstadt. Die Entdeckerin IOI-chan erkundet nun das Gebiet, in dem die Bibliothek stand. Aus den Ergebnissen ihrer Erkundung ist Folgendes bekannt:

• In der Bibliothek der Stadt JOI gab es ein waagerechtes Bücherregal. Es hatte $N$ Plätze in einer Reihe für Bücher, die von links nach rechts von $0$ bis $N-1$ nummeriert waren. Auf jeden Platz passte genau ein Buch.
• Im Bücherregal gab es $N$ Bücher. Die $N$ Bücher waren von $0$ bis $N-1$ nummeriert.
• Eine Anordnung der Bücher beschreibt, wie alle $N$ Bücher auf die $N$ Plätze gestellt werden.
• Es gab eine richtige Anordnung der Bücher. In dieser stand das Buch $B_i$ ($0 \le i \le N-1$) auf Platz $i$. Dabei sind alle $B_i$ verschieden.

Die Anordnung von Büchern ändert sich häufig. Wir wissen, dass in dieser Bibliothek die richtige Anordnung durch wiederholtes Ausführen der folgenden Operation wiederhergestellt wurde.

Operation: Sei Buch $x$ das am weitesten links stehende Buch unter den Büchern, deren Platz von ihrem Platz in der richtigen Anordnung abweicht. Sei außerdem Buch $y$ das Buch, das in der aktuellen Anordnung an dem Platz steht, an dem Buch $x$ in der richtigen Anordnung steht. Vertausche die Plätze von Buch $x$ und Buch $y$.

Obwohl IOI-chan die alten Bücher der Bibliothek gefunden hat, konnte sie die richtige Anordnung nicht ermitteln. Sie fand jedoch eine alte Maschine, die die Operationen am Bücherregal der Bibliothek verwaltete. Wenn wir eine Anordnung der $N$ Bücher angeben und eine Anfrage an die Maschine senden, antwortet sie mit der Anzahl der Operationen, die nötig sind, um alle Bücher wieder in die richtige Anordnung zu bringen. IOI-chan möchte die richtige Anordnung durch Anfragen an die Maschine herausfinden. Da die Maschine alt ist, darf sie höchstens $5\,000$ Anfragen an sie senden.

Schreibe ein Programm, das anhand der Informationen über das Bücherregal die richtige Anordnung der Bücher durch höchstens $5\,000$ Anfragen bestimmt.

Implementierungsdetails

Du musst eine Datei einreichen.

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

• void solve(int N)

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

  • Der Parameter $N$ ist die Anzahl $N$ der Bücher.

In library3.cpp kannst du die folgende Funktion aufrufen.

• int query(const std::vector<int> a)

  Mit dieser Funktion sendet IOI-chan eine Anfrage an die Maschine.

  • Der Parameter $a$ ist ein Array der Länge $N$ und gibt die Anordnung der $N$ Bücher an, die in der Anfrage angegeben werden soll. Das bedeutet, dass in der angegebenen Anordnung Buch a[i] ($0 \le i \le N-1$) auf Platz $i$ stehen muss.
  • Der Rückgabewert ist die Anzahl der Operationen, die ausgehend von der angegebenen Anordnung nötig sind, um alle Bücher wieder in die richtige Anordnung zu bringen.
  • Die Länge des Parameters $a$ muss $N$ sein. Andernfalls wird dein Programm mit Wrong Answer [1] bewertet.
  • Jedes Element des Parameters $a$ muss zwischen $0$ und $N-1$ liegen. Andernfalls wird dein Programm mit Wrong Answer [2] bewertet.
  • Jedes Element des Parameters $a$ muss von allen anderen verschieden sein. Andernfalls wird dein Programm mit Wrong Answer [3] bewertet.
  • Du darfst die Funktion query nicht öfter als $5\,000$ Mal aufrufen. Wird sie öfter als $5\,000$ Mal aufgerufen, wird dein Programm mit Wrong Answer [4] bewertet.

• void answer(std::vector<int> b)

  Durch Aufrufen dieser Funktion gibt dein Programm die richtige Anordnung der Bücher an.

  • Der Parameter $b$ ist ein Array der Länge $N$ und gibt die Anordnung der $N$ Bücher an, die als Antwort angegeben werden soll. Das bedeutet, dass in der ausgegebenen Anordnung Buch b[i] ($0 \le i \le N-1$) auf Platz $i$ stehen muss.
  • Die Länge des Parameters $b$ muss $N$ sein. Andernfalls wird dein Programm mit Wrong Answer [5] bewertet.
  • Jedes Element des Parameters $b$ muss zwischen $0$ und $N-1$ liegen. Andernfalls wird dein Programm mit Wrong Answer [6] bewertet.
  • Jedes Element des Parameters $b$ muss von allen anderen verschieden sein. Andernfalls wird dein Programm mit Wrong Answer [7] bewertet.
  • Die angegebene Anordnung muss die richtige Anordnung sein. Andernfalls wird dein Programm mit Wrong Answer [8] bewertet.
  • Die Funktion answer muss genau einmal aufgerufen werden. Wird sie öfter als $1$ Mal aufgerufen, wird dein Programm mit Wrong Answer [9] bewertet. Falls die Funktion answer beim Beenden der Funktion solve nicht aufgerufen wurde, wird dein Programm mit Wrong Answer [10] bewertet.

Wichtiger Hinweis

• 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. Es darf auf keine Weise mit anderen Dateien kommunizieren. Es darf jedoch Debugginginformationen auf der Standardfehlerausgabe ausgeben.

Kompilierung und Testlauf

Auf der Wettbewerbswebseite kannst du eine Archivdatei herunterladen, die einen Beispiel-Grader zum Testen deines Programms enthält. Das Archiv enthält außerdem eine Beispielquelldatei für dein Programm.

Der Beispiel-Grader ist die Datei grader.cpp. Zum Testen deines Programms lege grader.cpp, library3.cpp und library3.h im selben Verzeichnis ab und führe den folgenden Befehl zum Kompilieren aus. Stattdessen kannst du auch compile.sh aus dem Archiv ausführen.

g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp

Wenn die Kompilierung erfolgreich ist, wird die ausführbare Datei grader erzeugt.

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

Eingabe für den Beispiel-Grader

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

$$ \begin{array}{l} N\\ B_0\ B_1\ \cdots\ B_{N-1} \end{array} $$

$B_i$ ($0 \le i \le N-1$) ist die Nummer des Buches, das in der richtigen Anordnung auf Platz $i$ steht.

Ausgabe des Beispiel-Graders

Der Beispiel-Grader gibt die folgenden Informationen auf der Standardausgabe und der Standardfehlerausgabe aus (Anführungszeichen dienen der Verdeutlichung).

• Wenn dein Programm als korrekt bewertet wird, gibt er die Anzahl der Aufrufe von query als „Accepted: 3000“ aus.
• Wenn dein Programm mit irgendeiner Art von falscher Antwort bewertet wird, gibt der Beispiel-Grader deren Typ als „Wrong Answer [3]“ aus.

Wenn dein Programm die Bedingungen mehrerer Arten von falschen Antworten erfüllt, meldet der Beispiel-Grader nur eine davon.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $2 \le N \le 500$.
• $0 \le B_i \le N-1$ ($0 \le i \le N-1$).
• $B_i\ne B_j$ ($0 \le i<j \le N-1$).
• Alle gegebenen Werte sind ganze Zahlen.

Teilaufgaben

1. ($2$ Punkte) $N \le 6$.
2. ($19$ Punkte) $N \le 100$.
3. ($79$ Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Hier sind eine Beispieleingabe für den Beispiel-Grader und die entsprechenden Funktionsaufrufe.

Eingabe 1

4
2 0 3 1

Beispielhafte Funktionsaufrufe

Hinweis

Zum Beispiel gibt der Aufruf query([0, 1, 2, 3]) die Anordnung an, in der die Bücher $0,1,2,3$ auf den Plätzen $0,1,2,3$ stehen. Die Operation wird wie folgt wiederholt.

1. Vertausche die Plätze von Buch $0$ und Buch $1$. Die Bücher $1,0,2,3$ stehen auf den Plätzen $0,1,2,3$.
2. Vertausche die Plätze von Buch $1$ und Buch $3$. Die Bücher $3,0,2,1$ stehen auf den Plätzen $0,1,2,3$.
3. Vertausche die Plätze von Buch $3$ und Buch $2$. Die Bücher $2,0,3,1$ stehen auf den Plätzen $0,1,2,3$.

Da $3$ Operationen nötig sind, um alle Bücher wieder in die richtige Anordnung zu bringen, ist der Rückgabewert $3$.

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