Dies ist eine interaktive Aufgabe.

Am Vorabend der Eröffnung des Dessertfestivals arbeitet der Küchenchef mit größter Sorgfalt an der Spezialität seines Geschäfts — der „千层幻彩慕斯“. Dieses Dessert besteht aus $n$ Moussestücken mit unterschiedlichen Geschmacksrichtungen, die mit $0,1,\dots,n-1$ nummeriert sind.

In der Aufregung hat der Assistent jedoch versehentlich die Reihenfolge der Moussestücke durcheinandergebracht. Nun stehen sie von links nach rechts in einer Reihe und bilden eine unbekannte Positionspermutation $p=(p_0,p_1,\dots,p_{n-1})$, wobei $p_i$ die Nummer des Moussestücks an Position $i$ bezeichnet.

Um die genaue Position jedes Moussestücks zu bestimmen, kannst du ein Dessertprüfgerät verwenden. Wählst du drei paarweise verschiedene Positionen $x,y,z$, gibt das Prüfgerät die Summe der kleinsten und der größten Nummer unter diesen drei Moussestücken zurück:

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

Die Glocke zur Eröffnung wird gleich läuten. Kannst du mit einer begrenzten Anzahl von Prüfungen die tatsächliche Position jedes Moussestücks exakt rekonstruieren?

Es gibt eine Permutation $p$ der Länge $n$, deren Elemente genau $0,1,\ldots,n-1$ sind. Du kennst den Inhalt von $p$ nicht.

Du kannst drei paarweise verschiedene Indizes $x,y,z$ wählen. Die Interaktionsbibliothek gibt dann

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

zurück. Deine Aufgabe ist es, die gesamte Permutation zu rekonstruieren. Die Obergrenze für die Anzahl der Anfragen und die Berechnung der Punktzahl anhand der Anzahl der Anfragen werden weiter unten beschrieben.

Implementierungsdetails

Du musst und sollst keine Funktion main implementieren. Die eingereichte Quelldatei muss Folgendes enthalten:

#include "mousse.h"

Du musst die folgenden beiden Funktionen implementieren:

void init(int c);
std::vector<int> mousse(int c, int n);

• $c$ ist die Nummer der Teilaufgabe; $c=0$ bezeichnet das Beispiel. Jeder Testfall enthält genau eine Instanz. Für diesen Testfall ruft die Interaktionsbibliothek einmal init(c) und anschließend einmal mousse(c,n) auf.
• mousse muss ein Array der Länge $n$ zurückgeben, dessen Element an Index $i$ den Wert $p_i$ hat. Die Indizierung beginnt bei $0$.

Du kannst die folgende Funktion aufrufen, um eine Anfrage zu stellen:

int query(int x, int y, int z);

Es muss $0\le x,y,z < n$ gelten, und $x,y,z$ müssen paarweise verschieden sein. Die Funktion gibt $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$ zurück.

Testen des Programms

Die Anhänge enthalten mousse.h, die lokale Interaktionsbibliothek grader.cpp und das Beispielprogramm template_mousse.cpp. Speichere dein Programm als mousse.cpp. Im Verzeichnis dieser Aufgabe kannst du Folgendes ausführen:

g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.in

Die lokale Interaktionsbibliothek liest die verborgene Permutation aus der Standardeingabe. Dein Programm darf diese Daten nicht selbst lesen. Das Eingabeformat lautet:

• Die erste Zeile enthält zwei ganze Zahlen $c,n$.
• Die zweite Zeile enthält $p_0,p_1,\ldots,p_{n-1}$.

Bei einer richtigen Antwort gibt die Interaktionsbibliothek Correct! und Max queries used: Q aus, wobei $Q$ die Anzahl der Anfragen in diesem Testfall ist. Bei einer falschen Antwort gibt sie Wrong answer. aus. Wird eine ungültige Anfrage gestellt oder die Obergrenze für die Anzahl der Anfragen überschritten, gibt das Programm eine Fehlermeldung auf der Standardfehlerausgabe aus und beendet sich. Mit dem zusätzlichen Parameter -v kannst du die Anzahl der Anfragen für diesen Testfall anzeigen lassen.

Beispiele

Eingabe 1

0 10
0 2 9 1 5 8 3 7 6 4

Ausgabe 1

Correct!
Max queries used: 15

Hinweis

Beim Aufruf von query(0,1,2) sind die drei zugehörigen Werte beispielsweise $0,2,9$, und der Rückgabewert ist $0+9=9$. Das Referenzprogramm verwendet für diese Instanz $15$ Anfragen. Wenn du eine andere Strategie verwendest, kann diese Anzahl anders sein.

Beschränkungen

Für alle Testdaten gilt $n\in\{10,100,10^5\}$, und $p$ ist eine Permutation von $0\sim n-1$. Jeder Testfall enthält genau eine Instanz.

Für das Beispiel gilt $c=0$ und $n=10$; die Obergrenze für die Anzahl der Anfragen ist $1000$.

Teilaufgaben

Beachte:

• Die Interaktionsbibliothek ist nicht adaptiv. Die Permutation jedes Testfalls wird bereits vor dem Aufruf deines Programms festgelegt und ändert sich nicht als Reaktion auf die Anfragen.
• Du darfst die verborgene Permutation weder durch Lesen der Standardeingabe noch auf andere unerlaubte Weise ermitteln. Die Implementierung der Interaktionsbibliothek bei der endgültigen Bewertung kann sich von der lokalen Interaktionsbibliothek unterscheiden.

Wenn mousse in einem Testfall eine falsche Antwort zurückgibt, die Parameter von query ungültig sind oder die Anzahl der Anfragen $Q_{\max}$ für diese Teilaufgabe überschreitet, beträgt der Punktefaktor dieses Testfalls $0$.

In den Teilaufgaben $1,2$ erhältst du die volle Punktzahl der jeweiligen Teilaufgabe nur dann, wenn alle Testfälle korrekt gelöst werden.

Wenn in den Teilaufgaben $3,4$ der Punktefaktor irgendeines Testfalls $0$ ist, erhältst du für die jeweilige Teilaufgabe $0$ Punkte. Andernfalls sei $Q$ die größte Anzahl von Anfragen unter allen Testfällen dieser Teilaufgabe. Der Punktefaktor $f(Q)$ wird durch die folgende Tabelle bestimmt:

Falls $Q\le 99970$, gilt $f(Q)=100\%$. Liegt $Q$ zwischen zwei benachbarten Tabellenzeilen $(Q_i,f_i)$ und $(Q_{i+1},f_{i+1})$, gilt:

$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$

Die Punktzahl für Teilaufgabe $3$ beträgt $30f(Q)$, die für Teilaufgabe $4$ beträgt $60f(Q)$. Die endgültige Punktzahl wird auf $3$ Nachkommastellen gerundet.

Zeitlimit: $10\ \mathrm{s}$.

Speicherlimit: $512\ \mathrm{MiB}$.