CT60299

The Middle So Far at Misthollow

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the valley of Misthollow with crates of beacons, and Petra the valuer must account for every last one. Task: After each arrival, print the median of the stream so far — defined as the element at sorted position ceil(k/2) (1-based). Input format: First line: n. Second line: n integers. Output format: Print n medians space-separated. Constraints: 1 <= n <= 4000; -10^9 <= a[i] <= 10^9.

Example 1:

Input: 1653 683489484 792041102 -15610404 984920693 -701695197 -977100909 -603832380 -490924701 -239127595 32197313 -270391462 784102952 447411145 -61038456 -301922218 -482057855 -494511227 -693958533 956707234 520317731 164086183 86516596 664682362 169934379 -291096359 197048551 -190522613 -803298257 -991480211 33167283 803278962 234787069 -408217523 195897693 776497895 724588667 527410094 -95930001 -585806747 768650446 -345999463 -157781260 -112738582 -552384924 336164776 -493713832 -855475576 -810600695 -265541153 293425347 520905311 220454614 323158475 393702471 -687547970 -372833884 923485843 -512204142 867224154 6698620 -533035013 702602417 -812160557 158359468 -773109709 -321629022 301173413 -826343722 -896326914 -342370882 -858106205 -645930282 -988326733 -76372073 -647266409 163002275 -5…
Output: 683489484 683489484 683489484 683489484 683489484 -15610404 -15610404 -490924701 -239127595 -239127595 -239127595 -239127595 -15610404 -61038456 -61038456 -239127595 -239127595 -270391462 -239127595 -239127595 -61038456 -61038456 -15610404 -15610404 -15610404 -15610404 -15610404 -61038456 -61038456 -61038456 -15610404 -15610404 -15610404 -15610404 32197313 32197313 33167283 32197313 32197313 32197313 32197313 -15610404 -15610404 -61038456 -15610404 -61038456 -61038456 -95930001 -95930001 -95930001 -61038456 -61038456 -15610404 -15610404 -15610404 -61038456 -15610404 -61038456 -15610404 -15610404 -15610404 -15610404 -15610404 -15610404 -15610404 -61038456 -15610404 -61038456 -61038456 -95930001 -95930001 -112738582 -112738582 -112738582 -112738582 -112738582 -112738582 -157781260 -157781260…

Example 2:

Input: 3584 690965842 476058270 629968564 -790660192 -414308004 -903444693 -178191298 322242012 -92711279 236857700 -802264571 349549763 858178657 822058786 -462016454 141399969 -803992357 20852441 2146979 954388315 -761699264 -367880958 457810521 -606750913 482036719 423427311 913926645 -546217441 -767375058 -959214681 -769869480 -350832047 -545599628 528120936 -861293301 481149289 -778632636 786532180 -747689942 -486732162 -690934134 434937026 -123262023 -411007527 943712065 -393587170 -720363021 -953588655 658806110 644829181 178772938 -546318078 -100885955 -234749604 612726067 -295558391 -834515216 -250347869 127261239 -24710072 -82048364 -342280445 -554477605 -602754527 -24936614 761488706 -395786902 817743296 -912416997 -367451961 580699899 167680565 -144813537 623716314 -85302037 -20872495…
Output: 690965842 476058270 629968564 476058270 476058270 -414308004 -178191298 -178191298 -92711279 -92711279 -92711279 -92711279 236857700 236857700 236857700 141399969 141399969 20852441 20852441 20852441 20852441 2146979 20852441 2146979 20852441 20852441 141399969 20852441 20852441 2146979 2146979 -92711279 -92711279 -92711279 -92711279 -92711279 -92711279 -92711279 -92711279 -178191298 -178191298 -178191298 -123262023 -178191298 -123262023 -178191298 -178191298 -350832047 -178191298 -178191298 -123262023 -178191298 -123262023 -178191298 -123262023 -178191298 -178191298 -234749604 -178191298 -178191298 -123262023 -178191298 -178191298 -234749604 -178191298 -178191298 -178191298 -178191298 -178191298 -234749604 -178191298 -178191298 -144813537 -144813537 -123262023 -144813537 -123262023 -14481…

Example 3:

Input: 1932 -983527215 -855380379 679868082 -403699491 695434448 581867393 -735867823 75508669 528976234 -604049835 265847274 -312929723 -192869166 -471683101 -633254425 875901584 970261822 -184208643 -263942454 -784798796 959680224 -603046175 -161006315 -892710419 -504700247 722421127 965150020 -611556597 273204352 897954283 652433204 290192508 56242134 554634735 -528849818 -590598854 -938291454 -563466120 -856809812 946303251 -214637244 -468610988 847265907 692873269 -75471469 802862733 -413408322 244246616 162995619 810438834 788895359 -758542939 -396433456 -471219724 -914159151 404304462 944732784 -610059705 -441693721 -274105156 709447160 14535398 -611009555 -853800744 -872743026 -300201351 242447840 614184209 562814434 677128379 -852299857 938260775 -189160316 743542372 664035610 -663787673…
Output: -983527215 -983527215 -855380379 -855380379 -403699491 -403699491 -403699491 -403699491 75508669 -403699491 75508669 -312929723 -192869166 -312929723 -312929723 -312929723 -192869166 -192869166 -192869166 -263942454 -192869166 -263942454 -192869166 -263942454 -263942454 -263942454 -192869166 -263942454 -192869166 -192869166 -184208643 -184208643 -161006315 -161006315 -161006315 -184208643 -184208643 -192869166 -192869166 -192869166 -192869166 -214637244 -192869166 -192869166 -184208643 -184208643 -184208643 -184208643 -161006315 -161006315 -75471469 -161006315 -161006315 -184208643 -184208643 -184208643 -161006315 -184208643 -184208643 -192869166 -184208643 -184208643 -184208643 -192869166 -192869166 -214637244 -192869166 -192869166 -184208643 -184208643 -184208643 -184208643 -184208643 -1…

Constraints:

1 <= n <= 4000; -10^9 <= a[i] <= 10^9.

Loading...
Test Cases:No test cases
No test cases available.
The Middle So Far at Misthollow - MEDIUM Coding Problem | CodeTikki