CT61553

The Middle So Far of Stormrest

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Miller the tallyman watches over the cliffside roost of Stormrest's stores of ledgers. A careful computation stands between order and chaos. 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: 3652 -962822097 202630131 -161315485 74122455 -361332313 -102485112 -109173825 565120040 -547032968 -981744176 385186333 145339904 918754014 -561064518 335728247 574789061 596211160 -647010732 988660913 30833586 741110790 893234187 936599633 89725649 353021411 384020452 892421235 -593282000 906333628 -315595043 -413807962 -49455269 989234986 -510264165 -679039787 -11037496 636794734 -797623105 686941335 47504353 -260787804 -249656292 236020535 -713399083 234535096 379739853 706176560 489733987 39578470 986067098 248813167 -305356214 581410619 602546862 -143262344 -344693311 644643541 -477884437 -949252391 934396395 -376449491 -571125272 -964298548 263500342 826436538 -821196552 822146471 420955835 271680419 -895757407 -339563942 696260195 -680888412 194202156 -623608542 968901192 -32151461…
Output: -962822097 -962822097 -161315485 -161315485 -161315485 -161315485 -109173825 -109173825 -109173825 -161315485 -109173825 -109173825 -102485112 -109173825 -102485112 -102485112 74122455 -102485112 74122455 30833586 74122455 74122455 145339904 89725649 145339904 145339904 202630131 145339904 202630131 145339904 145339904 89725649 145339904 89725649 89725649 74122455 89725649 74122455 89725649 74122455 74122455 47504353 74122455 47504353 74122455 74122455 89725649 89725649 89725649 89725649 145339904 89725649 145339904 145339904 145339904 89725649 145339904 89725649 89725649 89725649 89725649 74122455 74122455 74122455 89725649 74122455 89725649 89725649 145339904 89725649 89725649 89725649 89725649 89725649 89725649 89725649 89725649 74122455 89725649 74122455 89725649 89725649 89725649 7412…

Example 2:

Input: 3100 -227546326 -532025873 136232179 -781487851 315954205 -450664882 -592822388 531191511 926340115 161132062 291084072 -280028921 -455175307 -908777891 -631482549 -252892150 -828773542 -788929951 47880826 157064687 -730965566 741528313 223129655 176159512 -366872360 332716982 -685968417 116904852 482977314 -566165149 190070150 -568944698 -187163543 395254766 -324334027 -269019037 353714363 929672536 -583948530 541571966 -64930760 53697844 -398189929 407984888 -813595491 397263419 408050237 -376239960 -152562302 446297851 -143712510 -505842079 5688471 507079304 940428053 444324084 -850649662 -630155623 922384832 146071404 213601339 -967001941 -124012679 -925422255 -286010863 -803559649 -62983596 538406681 988017675 -97019102 600265812 -194205099 833985324 -595159152 228802235 742261465 -29…
Output: -227546326 -532025873 -227546326 -532025873 -227546326 -450664882 -450664882 -450664882 -227546326 -227546326 136232179 -227546326 -227546326 -280028921 -280028921 -280028921 -280028921 -450664882 -280028921 -280028921 -280028921 -280028921 -252892150 -252892150 -252892150 -252892150 -252892150 -252892150 -227546326 -252892150 -227546326 -252892150 -227546326 -227546326 -227546326 -252892150 -227546326 -227546326 -227546326 -227546326 -187163543 -187163543 -187163543 -187163543 -187163543 -187163543 -64930760 -187163543 -152562302 -152562302 -143712510 -152562302 -143712510 -143712510 -64930760 -64930760 -64930760 -143712510 -64930760 -64930760 5688471 -64930760 -64930760 -124012679 -124012679 -143712510 -124012679 -124012679 -64930760 -97019102 -64930760 -97019102 -64930760 -97019102 -649…

Example 3:

Input: 2083 -271975612 471191314 715595922 597112291 99936954 475633990 311033089 -879593348 -33832658 289339382 368854385 -572999093 535429478 691871714 -842950855 633331934 -926564743 -617348426 -685114909 -742837503 -179960004 -919310106 -499990143 396937606 500247902 318879842 455669570 718454240 -667882399 402562838 -180370331 958744003 -917544887 27831726 -609801595 963022470 33401926 137666771 -345355526 978125946 -255032117 -636021580 253391671 11388396 -861409254 618139366 63969529 271235395 569944828 165862383 463285185 -202999614 -436348083 -963815540 752296123 545720449 149476850 -721034734 411373254 -853468562 -732930624 -777347781 -13444256 521543720 -87195365 775325833 211177222 148376893 594258959 226156475 580014428 64038813 -826603434 271992919 -853278114 477174721 81560776 -486…
Output: -271975612 -271975612 471191314 471191314 471191314 471191314 471191314 311033089 311033089 289339382 311033089 289339382 311033089 311033089 311033089 311033089 311033089 289339382 289339382 99936954 99936954 -33832658 -33832658 -33832658 99936954 99936954 289339382 289339382 289339382 289339382 289339382 289339382 289339382 99936954 99936954 99936954 99936954 99936954 99936954 99936954 99936954 33401926 99936954 33401926 33401926 33401926 63969529 63969529 99936954 99936954 137666771 99936954 99936954 63969529 99936954 99936954 137666771 99936954 137666771 99936954 99936954 63969529 63969529 63969529 63969529 63969529 99936954 99936954 137666771 137666771 148376893 137666771 137666771 137666771 137666771 137666771 137666771 99936954 137666771 137666771 137666771 137666771 137666771 12338…

Constraints:

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

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