| Fişierul intrare/ieşire: | chatggg.in, chatggg.out | Sursă | ad-hoc |
| Autor | Ciprian Oprisa | Adăugată de |  Ciprian Oprisa •cypry |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
ChatGGG
Gigel este încântat de evoluţia inteligenţei artificiale şi recent a aflat că cea mai recentă inovaţie în domeniu, un program numit ChatGGG este capabil să sorteze vectori. Fericit că nu mai e necesar să implementeze singur sortările, Gigel decide să se folosească de ChatGGG, dar este dezamăgit că licenţa de evaluare îi permite să sorteze doar subsecvenţe de dimensiuni egale cu jumătate din cea a vectorului dat. Mai mult, el poate să apeleze ChatGGG doar pe 3 subsecvenţe ale unui vector.
Scrieţi un program care pentru un vector dat de lungime N îl ajută pe Gigel să selecteze cele 3 subsecvenţe de lungime N/2 pe care le va trimite spre ChatGGG pentru sortare.
Notă: o subsecvenţă este un vector crescător şi distinct de indici între 1 şi N, în ordine crescătoare, nu neapărat consecutivi.
Se acceptă orice soluţie validă.
Date de intrare
Fişierul de intrare chatggg.in conţine pe prima linie numărul de teste T. Fiecare test este format din două linii. Pe prima linie se află numărul N, ce reprezintă dimensiunea vectorului A. Pe a doua linie a fiecărui test se află cele N elemente ale vectorului A, separate prin spaţii.
Date de ieşire
În fişierul de ieşire chatggg.out se vor scrie 3*T linii, câte 3 linii pentru fiecare test. Fiecare linie reprezintă o subsecvenţă de dimensiune exact N/2, ce va fi sortată. După sortarea celor 3 subsecvenţe, pe rând, vectorul de intrare A trebuie să fie sortat.
Restricţii
- 4 ≤ N ≤ 50000, N este divizibil cu 4
- 1 ≤ T ≤ 30
Exemplu
| chatggg.in | chatggg.out |
|---|---|
| 2 4 3 9 7 6 8 3 8 4 7 1 5 2 6 | 3 4 2 3 3 4 2 3 6 8 1 3 4 5 2 4 5 7 |
Explicaţie
În primul exemplu începem cu elementele 3, 9, 7, 6. Sortând subsecvenţa 3, 4 obţinem 3, 9, 6, 7. A doua operaţie constă în a sorta subsecvenţa 2, 3, iar şirul devine 3, 6, 9, 7. La ultima operaţie sortăm din nou secveţa 3, 4 obţinând şirul 3, 6, 7, 9 care este sortat.
