CT58426

Captain and the Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the gristmill of Rye Hollow opens only for a perfect tally of beacons. Captain means to find out. 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: 735 455270194 774739215 347391559 715878773 -889078822 -772161383 643386968 416821505 -371731728 -598277328 -765367239 767992777 838939417 -791221247 -497672261 -974612832 -80695191 -452957407 -773942427 -871964577 -414162308 972981937 553149160 780148450 -243143053 64362502 -945048027 348268734 -908513263 914565928 676711765 116443897 356355934 736188802 -305811471 -469738251 -269060312 -133201195 -1071981 237966014 539604380 -849282831 -463527652 -531436053 -165470705 239006886 286425127 333029772 535846972 624714801 -278899321 185076790 344110095 838452403 666309599 -896747296 354473490 588802120 -820595693 -617926689 903513693 368398418 -113420487 682194096 71009781 477372006 924544956 -191390423 922034330 190507078 844349602 -301218357 -230484241 200453978 158682593 384144990 -8230717…
Output: 455270194 455270194 455270194 455270194 455270194 347391559 455270194 416821505 416821505 347391559 347391559 347391559 416821505 347391559 347391559 -371731728 -80695191 -371731728 -371731728 -452957407 -414162308 -414162308 -371731728 -371731728 -243143053 -243143053 -243143053 -243143053 -243143053 -243143053 -80695191 -80695191 64362502 64362502 64362502 -80695191 -80695191 -133201195 -80695191 -80695191 -1071981 -80695191 -80695191 -133201195 -133201195 -133201195 -80695191 -80695191 -1071981 -1071981 -1071981 -1071981 64362502 64362502 116443897 64362502 116443897 116443897 116443897 64362502 116443897 116443897 116443897 116443897 116443897 116443897 185076790 116443897 185076790 185076790 190507078 185076790 185076790 185076790 185076790 185076790 185076790 185076790 190507078 1905…

Example 2:

Input: 107 -580048190 -803357815 522429514 791401290 -388657825 -124391603 200158659 634050021 335096822 105477066 395145482 891612113 427085394 -598266002 976151853 99836927 -406693813 587370627 -75397622 575507613 498200491 520558998 -678425920 -913191467 -814728520 624506615 804360021 685614457 375008567 857517206 343015648 173467683 -415036749 840031211 -253334585 -491115251 -25522885 141257651 770352767 711185077 9386046 61939120 789684960 -985662608 961174614 -330216826 140397674 560116420 -375643520 400408612 -211724341 -76545776 69605922 -7731944 730888405 255325565 -857955315 -323775933 -190654510 -277659245 -903129099 -239387145 522003296 -665997734 311806881 866673340 626344596 182420368 147139536 717446917 140137753 430366826 -299951361 -418987767 232775169 833199011 367190229 -174311…
Output: -580048190 -803357815 -580048190 -580048190 -388657825 -388657825 -124391603 -124391603 200158659 105477066 200158659 200158659 335096822 200158659 335096822 200158659 200158659 200158659 200158659 200158659 335096822 335096822 335096822 200158659 200158659 200158659 335096822 335096822 375008567 375008567 375008567 343015648 343015648 343015648 343015648 335096822 335096822 200158659 335096822 335096822 335096822 200158659 335096822 200158659 335096822 200158659 200158659 200158659 200158659 200158659 200158659 173467683 173467683 141257651 173467683 173467683 173467683 141257651 141257651 140397674 140397674 105477066 140397674 105477066 140397674 140397674 141257651 141257651 147139536 147139536 147139536 147139536 147139536 141257651 147139536 147139536 173467683 147139536 173467683 17…

Example 3:

Input: 774 -379524112 -293279996 226479031 -451731871 802959173 -231093337 909795392 165059156 -754518361 -229054316 393870195 -118750495 -785223083 520416667 454030780 179087543 622334365 -590789274 394716257 869551129 -451410569 259344704 754438265 -911258056 114137265 -614588414 703221183 -719350824 -951935715 -973003045 -554502265 776574145 -541980001 -732598790 19946553 -979226175 -599877863 528789392 -466780161 191884202 -591821954 -811220033 850394594 -307776169 -996681289 553382602 265347285 817509631 -348326742 844033689 -729607745 633836322 926047092 -270216573 431918695 975751406 101955229 -453626603 369304839 -462823570 -530316728 -463992869 995383420 -47249047 -257784023 151091303 -189548130 532229764 504833208 -684600117 -710283276 824167571 -368904735 -255776197 -131425495 -9670413…
Output: -379524112 -379524112 -293279996 -379524112 -293279996 -293279996 -231093337 -231093337 -231093337 -231093337 -229054316 -229054316 -229054316 -229054316 -118750495 -118750495 165059156 -118750495 165059156 165059156 165059156 165059156 179087543 165059156 165059156 114137265 165059156 114137265 114137265 -118750495 -118750495 -118750495 -118750495 -229054316 -118750495 -229054316 -229054316 -229054316 -229054316 -229054316 -229054316 -231093337 -229054316 -231093337 -231093337 -231093337 -229054316 -229054316 -229054316 -229054316 -229054316 -229054316 -118750495 -229054316 -118750495 -118750495 19946553 -118750495 19946553 -118750495 -118750495 -229054316 -118750495 -118750495 -118750495 -118750495 -118750495 -118750495 -47249047 -118750495 -118750495 -118750495 -118750495 -189548130 -13…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Captain and the Middle So Far - MEDIUM Coding Problem | CodeTikki