| Fişierul intrare/ieşire: | dispozitiv.in, dispozitiv.out | Sursă | Junior Challenge 2025 |
| Autor | Muresan Luca Valentin | Adăugată de |  Muresan Luca Valentin •LucaMuresan |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dispozitiv
În Tărâmul Ooo, Regele Gheaţă a aruncat un blestem asupra Prinţesei Gumiţă. Ea a primit un string binar a1 a2 ... aN, alcătuit din 0-uri şi 1-uri.
Pentru a rupe blestemul, Finn şi Jake au primit de la BMO un dispozitiv magic. Dispozitivul poate fi folosit pe orice subsecvenţă de lungime exact K, inversând fiecare bit din aceasta (adică 0 devine 1 şi 1 devine 0).
Scopul lor este să transforme întreg şirul în 0-uri, dacă este posibil.
Însă Regele Gheaţă nu stă degeaba. El intervine de Q ori, iar de fiecare dată schimbă (inversează) un singur bit din şir, la o poziţie aleasă de el. După fiecare astfel de modificare, Finn şi Jake trebuie să verifice din nou dacă şirul poate fi adus la forma cu toate 0-uri, folosind dispozitivul magic. În plus, ei trebuie sa verifice si pentru şirul initial.
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+1 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 |
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].
