| Fişierul intrare/ieşire: | permutare.in, permutare.out | Sursă | Lot Vrancea 2010, Baraj 2 |
| Autor | Andrei Dragus, Marius Dragus | Adăugată de |  Andrei Misarca •Mishu91 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | permutare.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.
