Fişierul intrare/ieşire:permutare.in, permutare.outSursăLot Vrancea 2010, Baraj 2
AutorAndrei Dragus, Marius DragusAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.2 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Permutare

Lavinia are o afinitate pentru permutări, aşa că ea împreună cu Andrei au propus următorul joc:
Dându-se un număr N şi N+1 elemente din mulţimea {0, 1, -1} trebuie să generaţi o permutare de lungime 2*N+1, care să respecte următoarele condiţii:

  • Dacă elementul x din şirul dat este 0, mediana primelor 2*x-1 elemente din permutare trebuie să fie egală cu media primelor 2*x-1 elemente din permutare.
  • Dacă elementul x din şirul dat este 1, mediana primelor 2*x-1 elemente din permutare trebuie să fie mai mică decât media primelor 2*x-1 elemente din permutare.
  • Dacă elementul x din şirul dat este -1, mediana primelor 2*x-1 elemente din permutare trebuie să fie mai mare decât media primelor 2*x-1 elemente din permutare.

Date de intrare

În fişierul de intrare permutare.in se găseşte numărul natural N cu semnificaţia din enunţ. Pe următoarea linie se vor afla N+1 numere din mulţimea {0, 1, -1} având seminificaţia din enunţ.

Date de ieşire

În fişierul de ieşire permutare.out se vor găsi 2*N+1 numere naturale reprezentând elementele permutării cerute.

Restricţii

  • N ≤ 100.000
  • Pentru 50% din teste N ≤ 2.000

Exemplu

permutare.inpermutare.out
4
0 -1 0 1 0
3 5 6 7 4 9 2 1 8

Explicaţie

Pentru primele 3 elemente media este 14/3 = 4.66, iar mediana 5, deci mediana este mai mare decât media.
Pentru primele 5 elemente media este 25/5, iar mediana 5, deci mediana este egală cu media.
Pentru primele 7 elemente media este 36/7 = 5.1, iar mediana este 5, deci media este mai mare decât mediana.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content