Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2017-05-28 01:12:15.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:brackets.in, brackets.outSursăACM-ICPC Faza Nationala 2017
AutorMihai CalanceaAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.25 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Brackets

Erai in camera ta, iti vedeai de treaba ta, treceai Trie-ul persistent in documentatia pentru Finala ACM. Deodata, bate cineva la usa. Vecinul de alaturi te roaga sa-i imprumuti doua parantezari corecte, pentru ca are niste prieteni in vizita si ar vrea sa joace un joc. Te uiti prin camera, vezi un treap rupt in doua sub masa, un FFT cu constanta un milion scrijelit pe oglinda, in final vezi si un sir de paranteze ramas intr-o cutie de pizza.

Te hotarasti sa partitionezi sirul tau de paranteze (care nu e neaparat corect) in exact doua subsiruri de lungime cat mai apropiata (fapt aparent important pentru jocul dubios al vecinului), astfel incat ambele sa fie siruri de paranteze corecte. Vrei sa scapi cu totul de parantezele astea, asa ca nu vei lasa niciuna in cutia de pizza.

Date de intrare

Fişierul de intrare brackets.in va contine pe prima sa linie T, numarul de teste. Structura unui test este urmatoarea: pe prima linie se afla un numar N, reprezentand numarul de paranteze din sir. Urmatoarea linie contine un sir de paranteze de lungime N.

Date de ieşire

În fişierul de ieşire brackets.out se vor afla multiple linii, reprezentand raspunsurile la testele corespunzatoare. Daca nu e posibil ca sirul din input sa fie partitionat in doua subsiruri de paranteze corecte, veti afisa "-1". Altfel, veti afisa numarul de paranteze din primul subsir, urmat de indicii acestui subsir. Apoi veti afisa numarul de paranteze din al doilea subsir, urmat de indicii acestui subsir. Indicii sunt numerotati de la 1 la N. Intersectia celor doua multimi de indici trebuie sa fie vida, iar reuniunea celor doua multimi trebuie sa fie egala cu {1, 2, ..., N}. Ambele multimi de indici trebuie afisate in ordine crescatoare.

Restricţii

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 10.000

Exemplu

brackets.inbrackets.out
2
8
((())())
6
()()))
4
1 3 5 8
4
2 4 6 7
-1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?