== include(page="template/taskheader" task_id="keymess") ==
!>problema/keymess?keymess2.png!
În Tărâmul Ooo, eşti trimis într-o misiune prin Labirintul Biţilor, unde fiecare poartă este încuiată cu o cheie magică. Există exact $N$ chei, fiecare inscripţionată cu un număr de la $0$ la $N$-1. Dar, evident, cineva le-a amestecat complet.
Singura ta unealtă este o maşinărie ciudată şi pe jumătate stricată, numită Oracolul Bitwise.
Dacă îi oferi două chei **diferite** $i$ şi $j$, în loc să îţi spună exact ce sunt, maşinăria va spune AND-ul bitwise al numerelor lor:
$query(i, j) = a{~i~} & a{~j~}$
Sarcina ta: reconstruieşte întreaga permutare amestecată de chei $a{~1~}, a{~2~}, … a{~n~}$ folosind numărul minim posibil de întrebări către Oracol.
Poveste şi cerinţă...
h2. Date de intrare
Pe prima linie se află $T$, numărul de teste. Descrierea fiecărui test este următoarea:
Prima şi singura linie a fiecărui test conţine un întreg $N$.
h2. Interacţiunea
Interacţiunea pentru fiecare test începe când numărul $N$ este citit.
Pentru a face un query, se afişează o linie în următorul format:
* $? i j$
După fiecare astfel de query interactorul vă va răspunde în stdin cu numărul $(a{~i~} & a{~j~})$.
Pentru a da un răspuns, se afişează o linie în următorul format:
* $! a{~1~} a{~2~} … a{~n~}$
Răspunsul nu va fi considerat la numărul de query-uri.
După aceea, continuaţi la următorul test sau terminaţi programul dacă este ultimul test.
Fişierul de intrare $keymess.in$ ...
Interactorul nu este adaptiv, ceea ce înseamnă că permutarea este predeterminată.
h2. Date de ieşire
După ce printaţi fiecare query, nu uitaţi să afişaţi end of line şi să daţi flush la output. Altfel veţi primi verdictul „Walltime limit exceeded”.
Dacă, la orice pas al interacţiunii, citiţi -1 în loc de date valide, soluţia voastră va primi verdictul „Query invalid” din cauza unui query invalid sau a oricărei alte greşeli.
În fişierul de ieşire $keymess.out$ ...
h2. Restricţii
Există două teste cu datele respective:
Primul test:
* $T = 1$
* $N = 2^6^$
Al doilea test:
* $T = 20$
* $N = 2^13^$
Funcţia care determină punctajul este următoarea:
Fie q = numărul de query-uri maxim din unul dintre teste
* $... ≤ ... ≤ ...$
|_. Număr query-uri |_. Punctaj |
| $10^6^ ≤ q$ | $0$ |
| $90000 ≤ q < 10^6^$ | $10$ | |
| $17700 < q ≤ 90000$ | $(-71 / 72300) * qs + (23798 / 241)$ |
| $16700 < q ≤ 17700$ | $e^((1000 - (qs - 16700)) / 334)^ + 80$ |
| $q ≤ 16700$ | $100$ |
De asemenea, dacă interactorul primeşte mai mult de 10^6^ query-uri in total programul va fi terminat şi veţi primi verdictul "Prea multe queryuri".
!problema/keymess?punctare.png!
Operatorul & (AND) este un operator binar care are ca rezultat numărul obţinut prin conjuncţia fiecărei perechi de biţi ce apar în reprezentarea în memorie a operanzilor:
$0 & 0 = 0$
$0 & 1 = 0$
$1 & 0 = 0$
$1 & 1 = 1$
* Pentru a da flush, puteţi folosi:
h2. Exemplu
fflush(stdout) sau cout.flush() în C++;
sys.stdout.flush() în Python;
verificaţi documentaţia pentru alte limbaje de programare.
table(example). |_. keymess.in |_. keymess.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h2. Exemplu
h3. Explicaţie
|_. stdin |_. stdout |_. Explicaţie |
|1| |Se citeşte T|
|4|Se citeşte N| |
| |? 1 2|Query cu i = 1, j = 2|
| $0$| |Se răspunde că (a{~1~} & a{~2~}) = 0|
| |$! 0 1 2 3$|Programul a presupus că a găsit permutarea şi a răspuns|
...
== include(page="template/taskfooter" task_id="keymess") ==
