== include(page="template/taskheader" task_id="keymess") ==
!>problema/keymess?keymess2.png!
Breasla Aventurierilor te-a trimis intr-o misiune prin Labirintul Bitilor, unde fiecare poarta este incuiata cu o cheie magica. Exista exact n chei, fiecare inscriptioanta cu un numar de la 0 la n-1. Dar, evident… cineva le-a amestecat complet! Nimeni nu mai stie ce cheie se afla in ce locas. O adevarata harababura — un Keymess.
Î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 unealta? O masinarie ciudata si pe jumatate stricata, numita Oracolul Bitwise.
Singura ta unealtă este o maşinărie ciudată şi pe jumătate stricată, numită Oracolul Bitwise.
Daca ii oferi doua chei diferite i si j, in loc sa iti spuna exact ce sunt, Oracolul sopteste doar AND-ul bitwise al numerelor lor:
interogare(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~}$
Maistrii Breslei rad nebuneste:
"Daca vrei sa deschizi portile si sa supravietuiesti in acest labirint, trebuie sa afli valoarea fiecarei chei! Dar ai grija: Oracolul cere tribut la fiecare intrebare, asa ca trebuie sa rezolvi totul cu cat mai putine interogari!"
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 intreaga permutare amestecata de chei a[0..n-1] folosind numarul minim posibil de intrebari catre Oracol.
h2. Date de intrare
Pe prima linie se află $T$, numărul de teste. Descrierea fiecărui test este următoarea:
h2. Date de intrare
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.
Fişierul de intrare $dispozitiv.in$ este organizat astfel:
Pentru a face un query, se afişează o linie în următorul format:
Pe prima linie se află $T$, numărul de teste.
* $? i j$
Pentru fiecare test:
După fiecare astfel de query interactorul vă va răspunde în stdin cu numărul $(a{~i~} & a{~j~})$.
* Pe prima linie se află $N$, $K$.
* Pe a doua linie se afla string-ul binar $a$ de lungime $N$.
* Pe a treia linie se află numărul $Q$.
* Pe următoarele $Q$ linii se află câte un număr $p$, cu semnificaţia că Regele Gheaţă a inversat bit-ul $p$.
Pentru a da un răspuns, se afişează o linie în următorul format:
h2. Date de ieşire
* $! a{~1~} a{~2~} … a{~n~}$
În fişierul de ieşire $dispozitiv.out$ se va afişa astfel:
Răspunsul nu va fi considerat la numărul de query-uri.
* Pentru fiecare test, se vor afişa $Q$ linii. Pe fiecare linie se va afla $YES$, daca toate valorile pot fi făcute $0$ sau $NO$ altfel.
După aceea, continuaţi la următorul test sau terminaţi programul dacă este ultimul test.
Interactorul nu este adaptiv, ceea ce înseamnă că permutarea este predeterminată.
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.
h2. Restricţii
* $1 ≤ T ≤ 10 000$
* $1 ≤ K ≤ N ≤ 200 000$
* $1 ≤ Q ≤ 200 000$
* Fie $S_N$ suma tuturor $N$-urilor dintr-un test de evaluare. Se garantează că $S_N ≤ 200 000$.
* Fie $S_Q$ suma tuturor $Q$-urilor dintr-un test de evaluare. Se garantează că $S_Q ≤ 200 000$.
Există două teste cu datele respective:
Primul test:
* $T = 1$
* $N = 2^6^$
|_. # |_. Punctaj |_. Restricţii |
| 1 | 6 | $S_N, S_Q <= 200$ |
| 2 | 15 | $S_N, S_Q <= 2 000$ |
| 3 | 7 | $K = N$ |
| 4 | 15 | $K = 2$ |
| 5 | 24 | $K ≤ 10$ |
| 6 | 33 | Fără alte restricţii |
Al doilea test:
h2. Exemplu
* $T = 20$
* $N = 2^13^$
|_. dispozitiv.in |_. dispozitiv.out |
| 3
5 2
01100
3
1
2
3
7 3
1010110
5
2
7
4
1
5
10 5
0011001001
2
2
3 | YES
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
a
|
h3. Explicaţie
Funcţia care determină punctajul este următoarea:
În primul test, şirul este iniţial $01100$ şi putem inversa substring-uri de lungime exact $K = 2$. $01100$ poate fi transformat în $00000$ prin inversarea substring-ului $[2, 3]$.
Fie q = numărul de query-uri maxim din unul dintre teste
După prima actualizare, şirul devine $11100$. Se pare că acesta nu poate fi transformat în $00000$.
|_. 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:
fflush(stdout) sau cout.flush() în C++;
sys.stdout.flush() în Python;
verificaţi documentaţia pentru alte limbaje de programare.
h2. Exemplu
După a doua actualizare, şirul devine $10100$, care poate fi transformat în şir de zerouri prin inversarea substring-ului $[1, 2]$ (şirul devine $01100$), apoi prin inversarea substring-ului $[2, 3]$.
|_. 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="dispozitiv") ==
== include(page="template/taskfooter" task_id="keymess") ==
