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

În tărâmul Ooo, esti 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₁, a₂, .. a_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:
* ! a₁ a₂ ... 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

Există un singur test cu urmatoarele date:

• T = 20
• N = 2^13

Functia care determina punctajul este urmatoarea:

Fie qs = numarul de query-uri

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 reprezentare în memorie a operanzilor:

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

• Pentru a da flush, puteti folosi:

fflush(stdout) sau cout.flush() in C++;
sys.stdout.flush() in Python;
verificati documentatia pentru alte limbaje de programare

Exemplu

Cum se trimit solutii?