Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | keymess.in, keymess.out | Sursă | Junior Challenge 2025 |
| Autor | Adăugată de |  Turcanu David •Turcanu_David | |
| Timp execuţie pe test | 3 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Keymess
Eşti 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.
Singura ta unealta este o masinarie ciudata si pe jumatate stricata, numita Oracolul Bitwise.
Daca ii oferi doua chei diferite i si j, in loc sa iti spuna exact ce sunt, masinaria va spune AND-ul bitwise al numerelor lor:
query(i, j) = a[i] & a[j]
Sarcina ta: Reconstruieşte intreaga permutare amestecata de chei a[1..n] folosind numarul minim posibil de intrebari catre Oracol.
Date de intrare
Pe prima linie se află T, numărul de teste. Descrierea fiecarui test este urmatoarea:
Prima si singura linie a fiecarui test contine un intreg N
Pentru fiecare test:
- Pe prima linie se află N, K.
Interactiunea
Interactiunea pentru fiecare test incepe cand numarul N este citit.
Pentru a face un query, se afiseaza o linie in urmatorul format:
* ? i j
După fiecare astfel de query interactorul vă va răspunde în stdin cu numarul (a[i] & a[j]).
Pentru a da un raspuns, se afiseaza o linie in urmatorul format:
* ! a1 a2 ... a[n]
Raspunsul nu este va fi considerat la numarul de query-uri.
Dupa aceea, continuati la urmatorul test sau terminati programul daca este ultimul test.
Interactorul nu este adaptiv, ceea ce inseamna ca permutarea este predeterminata.
Dupa ce printati fiecare query, nu uitati sa afisati end of line si sa dati flush la output. Altfel veti primi verdictul de "Walltime limit exceeded".
Daca, la orice pas al interactiunii, cititi -1 in loc de date valide, solutia voastra va primi verdictul de "Query invalid" din cauza unui query invalid sau orice altei greseli.
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.
| # | 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 |
Exemplu
| 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 |
Explicaţie
Î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].
După prima actualizare, şirul devine 11100. Se pare că acesta nu poate fi transformat în 00000.
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].
