Fişierul intrare/ieşire:permsplit.in, permsplit.outSursăAlgoritmiada 2013, Runda Finala
AutorPaul-Dan BaltescuAdăugată deGheorgheMihaiMihai Gheorghe GheorgheMihai
Timp execuţie pe test0.35 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inpermsplit.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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?