Fişierul intrare/ieşire:salturi.in, salturi.outSursăGrigore Moisil 2018, 9
AutorAlex Cociorva, Mircea Popoveniuc, Razvan SalajanAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Salturi

Pe vremuri, oraşul Târgu Mureş avea N turnuri de diverse înălţimi numerotate de la 1 la N. Cronicile existente amintesc de faptul că cetatea a găzduit cel mai mare concurs între N pitici în arta săritului din turn în turn, iar regulile competiţiei au fost următoarele:

  • fiecare pitic i va porni de pe turnul i;
  • un pitic aflat pe un turn k poate sări doar pe turnuri cu indici strict mai mici decât k;
  • piticii pot sări doar pe turnuri strict mai înalte decât turnul pe care se află;
  • dacă există mai multe turnuri pe care poate să sară, un pitic va sări pe turnul cu indicele cel mai mare;
  • când un pitic nu mai găseşte vreun turn pe care să poată sări, el se va opri;
  • scorul obţinut de fiecare pitic este egal cu numărul de turnuri pe care el le-a parcurs.

După sute de ani de la încheierea competiţiei, înălţimile turnurilor au fost uitate. Totuşi, cronicarii au consemnat scorurile pentru fiecare pitic.

Dându-se scorurile obţinute de fiecare pitic i din cei N pitici, să se afle înălţimile celor N turnuri de pe vremuri. Se considera corectă orice soluţie pentru care, respectându-se regulile competiţiei, piticii obţin scorurile date. Dacă scorurile nu sunt valide pentru nici o configuraţie de înălţimi de turnuri, atunci se va afişa -1.

Se doreşte să se afle răspunsurile pentru T astfel de probleme.

Date de intrare

Fişierul de intrare salturi.in conţine pe prima linie numărul natural T reprezentând numărul de teste din fişierul de intrare. Urmează apoi T teste. Fiecare test este descris pe câte două linii din fişier dupa cum urmează: pe prima linie se află numărul natural N reprezentând numărul de pitici ce au participat la competiţie; pe următoarea linie se află N numere naturale separate prin spaţiu cu semnificaţia că al i-lea număr reprezintă scorul obţinut de piticul i.

Date de ieşire

Fişierul de ieşire salturi.out trebuie să conţină T linii: pe linia k se află răspunsul pentru testul k. Dacă există soluţie pentru testul k, atunci linia k trebuie să conţină N numere naturale separate prin spaţiu cu semnificaţia că al i-lea număr reprezintă înălţimea turnului i. Dacă nu există soluţie pentru testul al k-lea, atunci linia k trebuie să conţină valoarea -1.

Restricţii

  • 1 <= T <= 5.
  • 1 <= N ≤ 250 000. Suma N-urilor dintr-un fişier este maxim 500 000.
  • Scorurile obţinute de pitici sunt numere naturale între 1 şi N.
  • Înălţimile turnurilor de pe vremuri sunt numere naturale între 1 şi 109.
  • Pentru teste în valoare de 30 de puncte, 1 <= N <= 1 000.
  • Problema va fi evaluată pe teste în valoare de 90 de puncte.
  • Exemplul va reprezenta teste în valoare de 10 puncte "din oficiu".

Exemplu

salturi.insalturi.out
2
5
1 1 2 1 2
4
1 3 2 1
3 4 2 6 3
-1

Explicaţie

Se dau T=2 teste în fişier.
Pentru primul test, N=5. Dacă înălţimile turnurilor sunt 3 4 2 6 3, piticii vor sări în felul următor:
Piticul 1 (iniţial pe turnul 1 de înălţime 3) nu are unde să sară. Scorul lui va fi 1.
Piticul 2 (iniţial pe turnul 2 de înălţime 4) nu are unde să sară. Scorul lui va fi 1.
Piticul 3 (iniţial pe turnul 3 de înălţime 2) va sări pe turnul 2 (de înălţime 4), iar apoi nu mai are unde să sară. Scorul lui va fi 2.
Piticul 4 (iniţial pe turnul 4 de înălţime 6) nu are unde să sară. Scorul lui va fi 1.
Piticul 5 (iniţial pe turnul 5 de înălţime 3) va sări pe turnul 4 (de înălţime 6), iar apoi nu mai are unde să sară. Scorul lui va fi 2.
Se obţin scorurile 1 1 2 1 2, deci soluţia este una validă.
Se poate observa că înălţimile turnurilor nu sunt unice, aşadar pot fi afişate şi alte soluţii.
Pentru al doilea test, N=4. Nu se poate obţine nici o configuraţie de înălţimi de turnuri pentru care să se poată obţine scorurile date, aşadar se afişează -1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?