Tato úloha je interaktivní.

Na pultu cukrárny Blecha stojí dvě řady pestrobarevných dvouvrstvých želé (horní vrstva je $a$, dolní vrstva je $b$). Podle místního pravidla „doplňkového tuhnutí“ je součet výšek horní a dolní vrstvy každého želé přesně $n+1$. Obsluha původně uspořádala obě řady podle výšek do dokonalých permutací $1 \sim n$, ale včera večer čilá bleší obsluha omylem na některých pozicích prohodila horní a dolní vrstvu!

Nyní se blíží zahájení každoročního festivalu sladkostí a obsluha musí obnovit původní uspořádání želé před prohozením (tedy posloupnost výšek horní vrstvy $a$ před prohozením).

Výšky želé nemůžete přímo pozorovat, ale můžete zadávat pokyny automatickému měřicímu zařízení cukrárny: určíte několik pozic $i$, zařízení na těchto pozicích prohodí horní a dolní vrstvu a vrátí rozdíl mezi největší a nejmenší výškou aktuální horní vrstvy (variační rozpětí) i rozdíl mezi největší a nejmenší výškou dolní vrstvy (variační rozpětí). Pozor: účinek každého prohození zůstává zachován.

Dokážete pomocí omezeného počtu prohození a měření úspěšně obnovit původní posloupnost horní vrstvy želé?

Interaktivní knihovna nejprve zvolí permutaci $p$ čísel $1\sim n$ a vytvoří permutaci $b_i=n+1-p_i$. Potom pro každý index $i$ nezávisle rozhodne, zda prohodí dvě čísla na pozici $i$. Pole získaná po těchto prohozeních označíme $a,b$. Vždy tedy platí $a_i+b_i=n+1$, ale $a,b$ již nemusí být permutacemi.

Znáte $n$, ale tato dvě pole neznáte. Můžete vybrat několik pozic a prohodit na nich $a_i,b_i$; interaktivní knihovna vám sdělí variační rozpětí obou polí po prohození. Účinek každého prohození zůstává zachován.

Vaším úkolem je obnovit pole $a$ před prvním dotazem. Odpověď se považuje za správnou i tehdy, když se vrácené pole shoduje s cílovým polem až po současném nahrazení každé jeho hodnoty $x$ hodnotou $n+1-x$.

Implementační detaily

Nemusíte a ani nesmíte implementovat funkci main.

Ve zdrojovém souboru recover.cpp musíte zahrnout hlavičkový soubor range.h a implementovat následující funkci:

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

• $c$ je číslo aktuální podúlohy; v ostrých testech má hodnotu $1,2,3,4$ a v příkladu hodnotu $0$. $n$ je délka pole. Interaktivní knihovna zavolá recover právě jednou pro každý test.
• Návratovou hodnotou musí být pole celých čísel délky $n$, které představuje $a$ před prvním dotazem, nebo jeho doplněk získaný nahrazením všech hodnot.

Můžete volat následující funkci:

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

• Indexy v positions musí být navzájem různé a patřit do $[0,n-1]$. Je dovoleno předat prázdné pole.
• Interaktivní knihovna na každém indexu v positions právě jednou prohodí aktuální $a_i,b_i$ a poté vrátí variační rozpětí aktuálního $a$ a variační rozpětí aktuálního $b$. Prohození se mezi dotazy kumulují, ale při vracení odpovědi musíte obnovit původní pole před prohozeními.
• Variační rozpětí je definováno jako největší hodnota pole minus jeho nejmenší hodnota. Protože vždy platí $b_i=n+1-a_i$, jsou obě variační rozpětí vždy stejná.
• Počet volání query nesmí překročit limit $Q_{\max}$ daného testu.

Interaktivní knihovna není adaptivní: počáteční pole jsou určena již před začátkem recover a jejich volba se nemění podle vašich dotazů. Interaktivní knihovna použitá při konečném hodnocení se může lišit od poskytnuté ukázkové knihovny. Váš program nesmí číst interní data interaktivní knihovny ani přímo pracovat se standardním vstupem a výstupem.

Lokální testování

Umístěte recover.cpp, range.h a přiložený grader.cpp do stejného adresáře a přeložte je pomocí C++17:

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

První řádek, který lokální interaktivní knihovna načítá, obsahuje $c,n,Q_{\max}$; druhý řádek obsahuje permutaci $p_0,\ldots,p_{n-1}$; třetí řádek obsahuje $n$ čísel $0/1$, přičemž $1$ znamená prohození na dané pozici před začátkem interakce. Prostřednictvím parametrů funkce dostanete pouze $c,n$; permutace, příznaky prohození a limit počtu dotazů nebudou vašemu programu přímo předány.

Je-li odpověď správná, lokální interaktivní knihovna vypíše na prvním řádku Correct! a na druhém řádku Queries used: Q, kde $Q$ je počet dotazů použitých během tohoto volání. Je-li odpověď nesprávná, vypíše Wrong answer.; pokud bylo rozhraní voláno neplatným způsobem, vypíše navíc důvod chyby na standardní chybový výstup.

Příklady

Vstup 1

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

Výstup 1

Correct!
Queries used: 16

Vysvětlení

V příkladu je před začátkem interakce $a=(3,6,1,4,5,5)$; jeho doplněk získaný nahrazením všech hodnot je $(4,1,6,3,2,2)$. Vrácení kteréhokoli z těchto polí je správné. První volání query({}) vrátí $(5,5)$. Uvedený výstup odpovídá běhu přiloženého vzorového programu; různé správné programy mohou použít různé počty dotazů.

Omezení

Pro všechny testy platí $1\le n\le 500$.

Skóre každé podúlohy se určí podle testu s nejnižším násobitelem skóre v dané podúloze; podrobnosti jsou uvedeny níže.

Hodnocení

Pokud recover vrátí nesprávnou odpověď, parametry query jsou neplatné nebo počet dotazů překročí $Q_{\max}$, získáte za daný test $0$ bodů.

Jinak získáte v podúlohách $1,2$ za daný test plný počet bodů. V podúlohách $3,4$ označme $Q$ skutečný počet dotazů použitých v daném testu. Násobitel skóre $f(Q)$ se vypočítá podle následující tabulky:

Skóre podúlohy $3$ je $40f(Q)$ a skóre podúlohy $4$ je $40f(Q)$. Konečné skóre se zaokrouhlí na $3$ desetinná místa.

Časový limit: $2\ \mathrm{s}$.

Paměťový limit: $512\ \mathrm{MiB}$.