CT62123

The Silver Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the desert outpost of Sandspire, Baron records each marks in a worn leather ledger. The guild wants answers, not guesses. 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: 3131 615741287 159605272 607569749 348160271 -735649376 -508929834 -665416754 -533407251 766736431 124801597 -484925334 328708057 -937063609 -543844063 -267248213 -796118763 -439548307 91756238 131092408 -785888979 -174139027 55608304 643711768 245615787 194688832 -375157462 898234689 382838174 140640070 -602996943 278508230 725071624 -945122652 -404187567 -75090198 -320622294 427975048 -946568096 -849886661 -883613839 981647042 -462824277 697746110 -189627899 -113407701 -643893670 -227696952 -409416266 667232420 -365315598 -28211252 63323047 623737668 -236360586 -250922800 -273031857 -433939052 -137963178 -570141063 740386220 -13884024 788513427 -568360745 184198353 -83182646 -222092015 923880237 -963420096 -619215450 -933088158 -262433539 280149407 173300641 94767714 272680755 292597663 …
Output: 615741287 159605272 607569749 348160271 348160271 159605272 159605272 -508929834 159605272 124801597 124801597 124801597 124801597 -484925334 -267248213 -484925334 -439548307 -439548307 -267248213 -439548307 -267248213 -267248213 -174139027 -174139027 55608304 -174139027 55608304 55608304 91756238 55608304 91756238 91756238 91756238 55608304 55608304 -75090198 55608304 -75090198 -75090198 -174139027 -75090198 -174139027 -75090198 -174139027 -113407701 -174139027 -174139027 -189627899 -174139027 -189627899 -174139027 -174139027 -113407701 -174139027 -174139027 -189627899 -189627899 -189627899 -189627899 -189627899 -174139027 -174139027 -174139027 -174139027 -137963178 -174139027 -137963178 -174139027 -174139027 -189627899 -189627899 -189627899 -174139027 -174139027 -137963178 -137963178 -13…

Example 2:

Input: 3399 442463314 816579526 -91446166 354827980 483416853 197365632 671561834 -705052151 -517380563 -912428102 -624441179 739923135 -783396269 870214406 -558280319 -910373583 -840070701 -94966537 4045422 -336040024 -266392905 985433418 980117591 528073276 362004208 -703924321 303827056 -904330185 -398629938 791569783 -187682539 -51541740 -191337910 -293591024 11890838 261402954 -234885869 446413855 -580495621 -795617419 -711398993 227043613 527132102 592814829 -313691161 -744133704 -833600297 746564912 -354184877 461764041 271752676 -105422749 583671646 -663307118 486370982 244256935 346826526 -20501683 -32897649 552343121 259793701 25867047 -728600281 928893042 -767814472 -577177631 591352995 631601866 885081705 -872658600 -589070511 780295343 -907066521 -574824369 -814431098 378470619 27314…
Output: 442463314 442463314 442463314 354827980 442463314 354827980 442463314 354827980 354827980 197365632 197365632 197365632 197365632 197365632 197365632 -91446166 -91446166 -94966537 -91446166 -94966537 -94966537 -94966537 -91446166 -91446166 4045422 -91446166 4045422 -91446166 -91446166 -91446166 -91446166 -91446166 -91446166 -94966537 -91446166 -91446166 -91446166 -91446166 -91446166 -94966537 -94966537 -94966537 -91446166 -91446166 -91446166 -94966537 -94966537 -94966537 -94966537 -94966537 -91446166 -94966537 -91446166 -94966537 -91446166 -91446166 -51541740 -51541740 -32897649 -32897649 -20501683 -20501683 -20501683 -20501683 -20501683 -32897649 -20501683 -20501683 4045422 -20501683 -20501683 -20501683 -20501683 -32897649 -32897649 -32897649 -20501683 -32897649 -20501683 -20501683 404542…

Example 3:

Input: 921 -243757107 691220611 26757905 -404838662 -821191845 -253546617 -207846799 712986503 89883363 -874590343 193063844 740762460 -764978094 521804524 199180287 -589452823 -373423286 -191252828 505122338 -696495263 906009466 582660542 899155088 702812657 -205337826 322867125 -497957096 -413569020 634626444 430222619 -350212461 -309981773 -351782656 -693690420 -503362333 -388961480 297956806 361856203 930555517 334220325 -673444525 852473755 -861479508 247528638 754912793 93361960 556847325 609709947 759268887 878294755 -203633251 -391331743 -930609115 257080560 -689094346 443651405 72578541 26991344 919233196 -149123124 347167061 765741409 794009507 -460560355 -519675624 54664927 625670288 946432455 -924289330 813780120 -160183173 -373302744 231891642 163337088 815354120 -384857793 -87236280…
Output: -243757107 -243757107 26757905 -243757107 -243757107 -253546617 -243757107 -243757107 -207846799 -243757107 -207846799 -207846799 -207846799 -207846799 26757905 -207846799 -207846799 -207846799 -191252828 -207846799 -191252828 -191252828 26757905 26757905 26757905 26757905 26757905 -191252828 26757905 26757905 26757905 -191252828 -191252828 -205337826 -205337826 -207846799 -205337826 -205337826 -191252828 -191252828 -191252828 -191252828 -191252828 -191252828 26757905 26757905 89883363 89883363 93361960 93361960 93361960 89883363 89883363 89883363 89883363 89883363 89883363 72578541 89883363 72578541 89883363 89883363 93361960 89883363 89883363 72578541 89883363 89883363 89883363 89883363 89883363 72578541 89883363 89883363 93361960 89883363 89883363 72578541 72578541 54664927 54664927 269…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.