Tato úloha je interaktivní.

V předvečer zahájení festivalu dezertů šéfkuchař pečlivě dotváří proslulou specialitu svého podniku — „千层幻彩慕斯“. Tento dezert se skládá z $n$ kousků mousse s různými příchutěmi, očíslovaných postupně $0,1,\dots,n-1$.

V nastalém zmatku však pomocník omylem pomíchal pořadí kousků mousse. Nyní jsou seřazeny vedle sebe zleva doprava a tvoří neznámou permutaci $p=(p_0,p_1,\dots,p_{n-1})$, kde $p_i$ označuje číslo kousku mousse umístěného na $i$-té pozici.

Abyste zjistili přesnou polohu každého kousku mousse, můžete použít přístroj na testování dezertů. Pokaždé zvolíte tři navzájem různé pozice $x,y,z$ a přístroj vrátí součet nejmenšího a největšího čísla těchto tří kousků mousse:

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

Zvon ohlašující zahájení se již chystá zaznít. Dokážete pomocí omezeného počtu testů přesně určit skutečnou polohu každého kousku mousse?

Je dána permutace $p$ délky $n$, jejíž prvky jsou právě $0,1,\ldots,n-1$. Konkrétní obsah $p$ neznáte.

Můžete zvolit tři navzájem různé indexy $x,y,z$ a interaktivní knihovna vrátí

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

Vaším úkolem je rekonstruovat celou permutaci. Maximální počet dotazů a způsob výpočtu skóre podle počtu dotazů jsou uvedeny níže.

Implementační detaily

Soutěžící nemusí a ani nemají implementovat funkci main. Odevzdaný zdrojový soubor musí obsahovat:

#include "mousse.h"

Musíte implementovat následující dvě funkce:

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

• $c$ je číslo podúlohy; $c=0$ označuje ukázkový příklad. Každý testovací případ obsahuje právě jednu instanci. Interaktivní knihovna pro daný testovací případ jednou zavolá init(c) a poté jednou zavolá mousse(c,n).
• mousse musí vrátit pole délky $n$, jehož $i$-tý prvek je $p_i$; indexy začínají od $0$.

Soutěžící mohou k položení jednoho dotazu zavolat následující funkci:

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

Musí platit $0\le x,y,z < n$ a $x,y,z$ musí být po dvojicích různé. Funkce vrátí $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$.

Testování programu

Přílohy obsahují mousse.h, lokální interaktivní knihovnu grader.cpp a ukázkový program template_mousse.cpp. Uložte svůj program jako mousse.cpp a v adresáři této úlohy můžete spustit:

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

Lokální interaktivní knihovna načítá skrytou permutaci ze standardního vstupu; program soutěžícího nesmí tato data sám načítat. Formát vstupu je následující:

• První řádek obsahuje dvě celá čísla $c,n$.
• Druhý řádek obsahuje $p_0,p_1,\ldots,p_{n-1}$.

Je-li odpověď správná, interaktivní knihovna vypíše Correct! a Max queries used: Q, kde $Q$ je počet dotazů v daném testovacím případě; je-li odpověď chybná, vypíše Wrong answer.. Při neplatném dotazu nebo překročení maximálního počtu dotazů program vypíše chybovou zprávu na standardní chybový výstup a skončí. Přidáním argumentu -v můžete zobrazit počet dotazů v daném testovacím případě.

Příklady

Vstup 1

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

Výstup 1

Correct!
Max queries used: 15

Poznámka

Například při volání query(0,1,2) jsou tři odpovídající hodnoty $0,2,9$ a vrácená hodnota je $0+9=9$. Referenční program pro tato data použije $15$ dotazů. Pokud použijete jinou strategii, může být tento počet jiný.

Omezení

Pro všechna testovací data platí $n\in\{10,100,10^5\}$ a $p$ je permutace hodnot $0\sim n-1$. Každý testovací případ obsahuje právě jednu instanci.

V ukázkovém příkladu je $c=0$, $n=10$ a maximální počet dotazů je $1000$.

Hodnocení

Upozornění:

• Interaktivní knihovna není adaptivní. Permutace každého testovacího případu je určena před zavoláním programu soutěžícího a v závislosti na dotazech se nemění.
• Soutěžící nesmí získávat skrytou permutaci čtením ze standardního vstupu ani jinými nepovolenými prostředky. Implementace interaktivní knihovny použité při finálním hodnocení se může lišit od lokální interaktivní knihovny.

Pokud v některém testovacím případě mousse vrátí chybnou odpověď, parametry query jsou neplatné nebo počet dotazů překročí $Q_{\max}$ dané podúlohy, je násobitel skóre pro tento testovací případ $0$.

V podúlohách $1,2$ lze získat plný počet bodů za danou podúlohu pouze tehdy, jsou-li správně vyřešeny všechny testovací případy.

V podúlohách $3,4$ získá podúloha $0$ bodů, pokud je násobitel skóre byť jediného testovacího případu $0$. Jinak označme $Q$ maximální počet dotazů ze všech testovacích případů dané podúlohy. Násobitel skóre $f(Q)$ je určen následující tabulkou:

Pokud $Q\le 99970$, pak $f(Q)=100\%$. Pokud $Q$ leží mezi dvěma sousedními řádky tabulky $(Q_i,f_i)$ a $(Q_{i+1},f_{i+1})$, platí:

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

Skóre podúlohy $3$ je $30f(Q)$ a skóre podúlohy $4$ je $60f(Q)$. Výsledné skóre se zaokrouhlí na $3$ desetinná místa.

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

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