| Fişierul intrare/ieşire: | costume.in, costume.out | Sursă | Baraj Sumen 2013 juniori runda 2 |
| Autor | Catalin Francu, Victor Manz | Adăugată de |  Catalin Francu •Catalin.Francu |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 4096 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.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, indicând 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 ≤ 200.000
- pentru 20% din teste, 1 ≤ N ≤ 20.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.
