Keymess

keymess

== 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.

Î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~}$

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.

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.

h2. Date de intrare

Prima şi singura linie a fiecărui test conţine un întreg $N$.

Pentru fiecare test:
 
* Pe prima linie se află $N$, $K$.
 

h2. Interacţiunea
Interacţiunea pentru fiecare test începe când numărul $N$ este citit.

* $? i j$

După fiecare astfel de query interactorul vă va răspunde în stdin cu numărul $(a{~i~} & a{~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:

h2. Restricţii

Există două teste cu datele respective:
 
Primul test:
 
* $T = 1$
* $N = 2^6^$
 
Al doilea test:

Există un singur test cu următoarele date:

* $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

Fie qs = numărul de query-uri

|_. 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$

| qs ≤ 16700           | 100                                            |
| 16700 < qs ≤ 17700   | e^((1000 - (qs - 16700)) / 334) + 80^        |
| 17700 < qs ≤ 90000   | (-71 / 72300) * qs + (23798 / 241)                                     |
| 90000 ≤ qs < 2^26^   | 10                                             |
| 2^26^ ≤ qs           | $0$                                             |
 
Operatorul de conjuncţie biţi & (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: