Dies ist eine interaktive Aufgabe.

Auf der Theke des Dessertladens 跳蚤 stehen zwei Reihen bunter, zweischichtiger Gelees (die obere Schicht ist $a$, die untere Schicht ist $b$). Aufgrund der Regel der „komplementären Erstarrung“ des Ladens beträgt die Summe der Höhen der oberen und unteren Schicht jedes Gelees genau $n+1$. Ursprünglich hatten die Angestellten diese beiden Reihen nach ihrer Höhe zu perfekten Permutationen von $1 \sim n$ angeordnet, doch gestern Abend vertauschte der lebhafte Angestellte 跳蚤 versehentlich an einigen Positionen die oberen und unteren Geleeschichten!

Nun steht das jährliche Dessertfest kurz vor der Eröffnung, und die Angestellten müssen die ursprüngliche Anordnung vor dem Vertauschen der Geleeschichten wiederherstellen (also die Höhenfolge $a$ der oberen Geleeschichten vor dem Vertauschen).

Du kannst die Höhen der Gelees nicht direkt beobachten, aber du kannst dem automatischen Messgerät des Dessertladens Befehle geben: Gib einige Positionen $i$ an. Das Messgerät vertauscht für dich an diesen Positionen die oberen und unteren Geleeschichten und gibt die Differenz zwischen der maximalen und der minimalen Höhe (die Spannweite) der aktuellen oberen Geleeschichten sowie die Differenz zwischen der maximalen und der minimalen Höhe (die Spannweite) der unteren Geleeschichten zurück. Achtung: Die Wirkung jedes Vertauschens bleibt bestehen.

Kannst du die ursprüngliche Anordnung der oberen Geleeschichten mit einer begrenzten Anzahl solcher Vertauschungs- und Messvorgänge erfolgreich wiederherstellen?

Die Interaktionsbibliothek wählt zunächst eine Permutation $p$ von $1\sim n$ und konstruiert die Permutation $b_i=n+1-p_i$. Anschließend entscheidet die Interaktionsbibliothek für jeden Index $i$ unabhängig, ob sie die beiden Zahlen an Position $i$ vertauscht. Die nach diesen Vertauschungen entstandenen Arrays werden mit $a,b$ bezeichnet. Dann gilt stets $a_i+b_i=n+1$, aber $a,b$ sind nicht unbedingt weiterhin Permutationen.

Du kennst $n$, aber nicht diese beiden Arrays. Du kannst einige Positionen auswählen und an diesen Positionen $a_i,b_i$ vertauschen; die Interaktionsbibliothek teilt dir die Spannweiten der beiden Arrays nach dem Vertauschen mit. Die Wirkung jedes Vertauschens bleibt bestehen.

Deine Aufgabe besteht darin, das Array $a$ vor der ersten Anfrage wiederherzustellen. Auch wenn das zurückgegebene Array erst dann mit dem gesuchten Array übereinstimmt, wenn jeder seiner Werte $x$ gleichzeitig durch $n+1-x$ ersetzt wird, gilt die Antwort als korrekt.

Implementierungsdetails

Du musst und sollst keine main-Funktion implementieren.

Du musst in der Quelldatei recover.cpp die Headerdatei range.h einbinden und die folgende Funktion implementieren:

std::vector<int> recover(int c, int n);

• $c$ ist die Nummer der aktuellen Teilaufgabe und hat in den offiziellen Tests einen der Werte $1,2,3,4$; im Beispiel ist sie $0$. $n$ ist die Länge der Arrays. Die Interaktionsbibliothek ruft recover für jeden Testfall genau einmal auf.
• Der Rückgabewert muss ein Array ganzer Zahlen der Länge $n$ sein, das $a$ vor der ersten Anfrage oder dessen vollständiges Komplement darstellt.

Du kannst die folgende Funktion aufrufen:

std::pair<int, int> query(const std::vector<int>& positions);

• Die Indizes in positions müssen paarweise verschieden sein und in $[0,n-1]$ liegen. Ein leeres Array darf übergeben werden.
• Die Interaktionsbibliothek vertauscht für jeden Index in positions genau einmal die aktuellen Werte $a_i,b_i$ und gibt anschließend die Spannweite des aktuellen Arrays $a$ und die Spannweite des aktuellen Arrays $b$ zurück. Die Vertauschungen zwischen den Anfragen akkumulieren sich, aber bei der Rückgabe der Antwort musst du das ursprüngliche Array vor den Vertauschungen wiederherstellen.
• Die Spannweite ist als der maximale Wert des Arrays minus dessen minimalen Wert definiert. Da stets $b_i=n+1-a_i$ gilt, sind die beiden Spannweiten immer gleich.
• Die Anzahl der Aufrufe von query darf die Obergrenze $Q_{\max}$ des jeweiligen Testfalls nicht überschreiten.

Die Interaktionsbibliothek ist nicht adaptiv: Die ursprünglichen Arrays stehen bereits vor Beginn von recover fest und ändern sich nicht in Abhängigkeit von deinen Anfragen. Die bei der endgültigen Bewertung verwendete Interaktionsbibliothek kann von der bereitgestellten Beispielbibliothek abweichen. Dein Programm darf weder interne Daten der Interaktionsbibliothek lesen noch direkt auf die Standardeingabe oder Standardausgabe zugreifen.

Testen des Programms

Lege recover.cpp, range.h und die in den Anhängen enthaltene Datei grader.cpp in dasselbe Verzeichnis und kompiliere sie mit C++17:

g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.in

Die erste Zeile, die die lokale Interaktionsbibliothek einliest, enthält $c,n,Q_{\max}$; die zweite Zeile enthält die Permutation $p_0,\ldots,p_{n-1}$; die dritte Zeile enthält $n$ Zahlen mit den Werten $0/1$, wobei $1$ bedeutet, dass an dieser Position vor Beginn der Interaktion vertauscht wird. Nur $c,n$ werden dir über die Funktionsparameter bereitgestellt; die Permutation, die Vertauschungsmarkierungen und die Anfrageobergrenze werden deinem Programm nicht direkt übergeben.

Ist die Antwort korrekt, gibt die lokale Interaktionsbibliothek in der ersten Zeile Correct! und in der zweiten Zeile Queries used: Q aus, wobei $Q$ die Anzahl der bei diesem Aufruf verwendeten Anfragen ist. Ist die Antwort falsch, gibt sie Wrong answer. aus; ist ein Schnittstellenaufruf ungültig, wird zusätzlich der Fehlergrund auf der Standardfehlerausgabe ausgegeben.

Beispiele

Eingabe 1

0 6 67
3 1 6 4 2 5
0 1 1 0 1 0

Ausgabe 1

Correct!
Queries used: 16

Hinweis

Im Beispiel ist vor Beginn der Interaktion $a=(3,6,1,4,5,5)$; dessen vollständiges Komplement ist $(4,1,6,3,2,2)$. Die Rückgabe eines dieser beiden Arrays ist korrekt. Der erste Aufruf von query({}) gibt $(5,5)$ zurück. Die obige Ausgabe entspricht dem Ergebnis des in den Anhängen enthaltenen Referenzprogramms; verschiedene korrekte Programme können unterschiedlich viele Anfragen verwenden.

Beschränkungen

Für alle Testdaten gilt $1\le n\le 500$.

Jede Teilaufgabe wird anhand des Testfalls mit dem niedrigsten Bewertungsfaktor innerhalb dieser Teilaufgabe bewertet; Einzelheiten folgen unten.

Teilaufgaben

Wenn die von recover zurückgegebene Antwort falsch ist, die Parameter von query ungültig sind oder die Anzahl der Anfragen $Q_{\max}$ überschreitet, erhält dieser Testfall $0$ Punkte.

Andernfalls erhält der Testfall in den Teilaufgaben $1,2$ die volle Punktzahl. In den Teilaufgaben $3,4$ sei $Q$ die tatsächlich für diesen Testfall verwendete Anzahl der Anfragen. Der Bewertungsfaktor $f(Q)$ wird anhand der folgenden Tabelle berechnet:

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

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

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