Atenție! Aceasta este o versiune veche a paginii., scrisă la 2013-10-30 15:47:36.
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 avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii