| Fişierul intrare/ieşire: | permsplit.in, permsplit.out | Sursă | Algoritmiada 2013, Runda Finala |
| Autor | Paul-Dan Baltescu | Adăugată de |  Mihai Gheorghe •GheorgheMihai |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Permsplit
Se da o permutare a multimii {1..N}. O subsecventa se numeste compacta daca toate numerele din subsecventa formeaza un interval compact de numere naturale (exemplu: 2 4 3 5 e o secventa compacta, 1 4 3 nu e o secventa compacta). Sa se efectueze N-1 taieturi asupra permutarii initiale astfel incat la fiecare pas subsecventele obtinute se fie compacte sau se spuna daca acest lucru este imposibil.
Date de intrare
Fişierul de intrare permsplit.in contine pe prima linie numarul N si pe a doua linie o permutare de N elemente.
Date de ieşire
În fişierul de ieşire permsplit.out se vor afisa pe prima linie N-1 numere, al i-lea numar reprezentand pozitia elementului din permutarea dupa care se face taietura. In cazul in care nu exista solutie, sa se afiseze -1.
Restricţii
- 2 ≤ N ≤ 1.000.000
Exemplu
| permsplit.in | permsplit.out |
|---|---|
| 5 1 5 3 4 2 | 1 2 4 3 |
Explicaţie
(1 5 3 4 2)
(1) (5 3 4 2)
(1) (5) (3 4 2)
(1) (5) (3 4) (2)
(1) (5) (3) (4) (2)
