Detta är en interaktiv uppgift.

På disken i 跳蚤s dessertbutik står två rader av färgglada geléer med två lager (det övre lagret är $a$ och det undre är $b$). Enligt butikens regel om ”kompletterande stelning” är summan av det övre och det undre lagrets höjd i varje gelé exakt $n+1$. Personalen hade ursprungligen ordnat de två raderna efter höjd så att de bildade perfekta permutationer av $1 \sim n$, men i går kväll råkade den livliga butiksanställda 跳蚤 byta plats på geléernas övre och undre lager på vissa positioner!

Nu ska den årliga dessertfestivalen snart öppna, och personalen måste återställa geléernas ursprungliga placering före omkastningarna (alltså höjdföljden $a$ för de övre gelélagren före omkastningarna).

Du kan inte observera geléernas höjder direkt, men du kan ge instruktioner till dessertbutikens automatiska mätinstrument: ange ett antal positioner $i$, så byter instrumentet plats på de övre och undre gelélagren på dessa positioner och returnerar skillnaden mellan den största och den minsta höjden (variationsbredden) i det aktuella övre lagret, samt skillnaden mellan den största och den minsta höjden (variationsbredden) i det undre lagret. Observera: effekten av varje omkastning kvarstår.

Kan du återställa den ursprungliga följden av övre gelélager med ett begränsat antal omkastningar och mätningar?

Interaktionsbiblioteket väljer först en permutation $p$ av $1\sim n$ och konstruerar permutationen $b_i=n+1-p_i$. För varje index $i$ bestämmer biblioteket sedan oberoende om de två talen på position $i$ ska byta plats. De arrayer som erhålls efter dessa byten betecknas med $a,b$. Då gäller alltid $a_i+b_i=n+1$, men $a,b$ behöver inte längre vara permutationer.

Du känner till $n$, men inte de två arrayerna. Du kan välja ett antal positioner och byta plats på $a_i,b_i$ på dessa positioner; interaktionsbiblioteket meddelar variationsbredden för de två arrayerna efter bytena. Effekten av varje byte kvarstår.

Din uppgift är att återställa arrayen $a$ före den första frågan. Svaret anses också korrekt om den returnerade arrayen blir lika med målarrayen först när varje värde $x$ samtidigt ersätts med $n+1-x$.

Implementationsdetaljer

Du behöver inte, och ska inte, implementera funktionen main.

Du ska inkludera headerfilen range.h i källfilen recover.cpp och implementera följande funktion:

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

• $c$ är numret på den aktuella deluppgiften och är $1,2,3,4$ i de officiella testerna och $0$ i exemplet. $n$ är arrayens längd. Interaktionsbiblioteket anropar recover exakt en gång per testfall.
• Returvärdet måste vara en heltalsarray av längd $n$ som representerar $a$ före den första frågan, eller dess komplement där alla element ersätts samtidigt.

Du kan anropa följande funktion:

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

• Indexen i positions måste vara parvis olika och tillhöra $[0,n-1]$. En tom array får anges.
• Interaktionsbiblioteket byter plats på de aktuella värdena $a_i,b_i$ exakt en gång för varje index i positions och returnerar sedan variationsbredden för aktuella $a$ och variationsbredden för aktuella $b$. Bytena ackumuleras mellan frågorna, men när du returnerar svaret ska du återställa den ursprungliga arrayen före bytena.
• Variationsbredden definieras som arrayens största värde minus dess minsta värde. Eftersom $b_i=n+1-a_i$ alltid gäller, är de två variationsbredderna alltid lika.
• Antalet anrop till query får inte överstiga gränsen $Q_{\max}$ för det aktuella testfallet.

Interaktionsbiblioteket är inte adaptivt: de ursprungliga arrayerna bestäms innan recover börjar och ändras inte som svar på dina frågor. Biblioteket som används vid den slutliga bedömningen kan skilja sig från det medföljande exempelbiblioteket. Ditt program får inte läsa bibliotekets interna data eller direkt använda standardindata eller standardutdata.

Testning av programmet

Lägg recover.cpp, range.h och den bifogade filen grader.cpp i samma katalog och kompilera med C++17:

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

Den första raden som det lokala interaktionsbiblioteket läser innehåller $c,n,Q_{\max}$; den andra innehåller permutationen $p_0,\ldots,p_{n-1}$; den tredje innehåller $n$ tal som är $0/1$, där $1$ betyder att ett byte sker på den positionen innan interaktionen börjar. Endast $c,n$ tillhandahålls via funktionsparametrarna; permutationen, bytesmarkeringarna och frågegränsen skickas inte direkt till ditt program.

Om svaret är korrekt skriver det lokala interaktionsbiblioteket Correct! på den första raden och Queries used: Q på den andra, där $Q$ är antalet frågor som användes under detta anrop. Om svaret är fel skriver det Wrong answer.; om ett gränssnittsanrop är ogiltigt anges dessutom orsaken på standardfelströmmen.

Exempel

Indata 1

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

Utdata 1

Correct!
Queries used: 16

Förklaring

I exemplet är $a=(3,6,1,4,5,5)$ innan interaktionen börjar; dess komplement är $(4,1,6,3,2,2)$. Båda är korrekta returvärden. Det första anropet till query({}) returnerar $(5,5)$. Utdata ovan är resultatet från den bifogade referenslösningen; olika korrekta program kan använda olika antal frågor.

Begränsningar

För alla testdata gäller $1\le n\le 500$.

Varje deluppgift poängsätts utifrån det testfall som har den lägsta poängmultiplikatorn inom deluppgiften. Detaljer följer nedan.

Poängsättning

Om recover returnerar ett felaktigt svar, om argumenten till query är ogiltiga eller om antalet frågor överstiger $Q_{\max}$, får testfallet $0$ poäng.

Annars får testfallet full poäng för deluppgifterna $1,2$. För deluppgifterna $3,4$, låt $Q$ vara antalet frågor som faktiskt används i testfallet. Poängmultiplikatorn $f(Q)$ beräknas enligt följande tabell:

Poängen för deluppgift $3$ är $40f(Q)$ och poängen för deluppgift $4$ är $40f(Q)$. Slutpoängen avrundas till $3$ decimaler.

Tidsgräns: $2\ \mathrm{s}$.

Minnesgräns: $512\ \mathrm{MiB}$.