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
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.
Singura ta unealta? 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, Oracolul sopteste doar AND-ul bitwise al numerelor lor:
interogare(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 intreaga permutare amestecata de chei a[0..n-1] folosind numarul minim posibil de intrebari catre Oracol.
Date de intrare
Fişierul de intrare dispozitiv.in este organizat astfel:
Pe prima linie se află T, numărul de teste.
Pentru fiecare test:
- 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.
Date de ieşire
În fişierul de ieşire dispozitiv.out se va afişa astfel:
- 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.
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].
