Revizia anterioară Revizia următoare
Fișierul intrare/ieșire | costume.in, costume.out | Sursă | Baraj Sumen 2013 juniori runda 2 |
---|---|---|---|
Autor | Cătălin Frâncu | Victor Manz | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 4096 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Costume
Un magazin de costume de Halloween a comandat N costume, toate diferite. Înainte de a plasa comanda, proprietarul a numerotat costumele în ordinea gradului de urâțenie, de la 1 (cel mai urât) la N (cel mai frumos). Dintr-o eroare de aprovizionare, costumele ajung la magazin câte unul pe zi. Proprietarul vrea să expună zilnic în vitrină costumul de urâțenie mediană din cele pe care le are în stoc. Un costum prea urât ar speria clienții, iar un costum prea frumos... e totuși Halloween! Ajutați-l pe proprietar să expună zilnic costumul potrivit. Notă: proprietarul nu vinde niciun costum, deoarece totul se petrece în aprilie.
Medianul unei mulțimi de 2k + 1 numere este al k+1$-lea număr ca valoare. Medianul unei mulțimi de $2k numere, pentru problema noastră, este al k-lea număr ca valoare.
Date de intrare
Fișierul de intrare costume.in conține pe prima linie numărul N de costume. Pe a doua linie apar N numere, în ordinea în care ajung costumele la magazin.
Date de ieșire
În fișierul de ieșire costume.out se vor scrie N numere despărțite prin spații. Al i-lea număr reprezintă costumul care trebuie expus în ziua i.
Restricții
- 1 ≤ N ≤ 500.000
- pentru 20% din teste, 1 ≤ N ≤ 30.000
Exemplu
costume.in | costume.out |
---|---|
9
2 9 7 1 4 3 5 8 6 |
2 2 7 2 4 3 4 4 5 |
Explicație
- În prima zi, unicul costum este 2, care trebuie expus.
- În ziua a doua, dintre costumele {2, 9}, medianul este 2.
- În ziua a treia, dintre costumele {2, 7, 9}, medianul este 7.
- În ziua a patra, dintre costumele {1, 2, 7, 9}, medianul este 2.
- etc.