CT62957

The marks at Masthead

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the galleon yard of Masthead, Trader 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: 637 -266452489 -324291581 -117155408 882725748 -370986890 -900990371 -783292317 849664431 217379181 -239667608 593982655 921418014 112664831 102487730 243751831 433998404 519162102 330463339 -324840882 -218091318 -526668071 -87532182 -991436891 875901342 -918351657 -649656149 148050266 -593169451 364213561 -344505448 532252337 480692287 -969935099 -462401554 335378370 -196519070 -985324702 6642509 -319846096 899870638 -61894290 289171224 -774674252 194992110 -964713525 194747695 337522813 -927070604 -413924101 397985490 -993766700 -640554223 317961502 -410983628 358855112 -656629783 -176788463 193449374 938924807 801174860 -606921768 -422200323 -232427744 389508194 388089493 653545419 -76710406 573824613 -790176733 -798898110 -319082727 896773803 -803259897 205877205 -931040048 317637193 2…
Output: -266452489 -324291581 -266452489 -266452489 -266452489 -324291581 -324291581 -324291581 -266452489 -266452489 -239667608 -239667608 -117155408 -117155408 102487730 102487730 112664831 112664831 112664831 102487730 102487730 -87532182 -87532182 -87532182 -87532182 -117155408 -87532182 -117155408 -87532182 -117155408 -87532182 -87532182 -87532182 -117155408 -87532182 -117155408 -117155408 -117155408 -117155408 -117155408 -87532182 -87532182 -87532182 -87532182 -87532182 -87532182 -61894290 -87532182 -87532182 -87532182 -87532182 -117155408 -87532182 -117155408 -87532182 -117155408 -117155408 -117155408 -87532182 -87532182 -87532182 -117155408 -117155408 -117155408 -87532182 -87532182 -76710406 -76710406 -76710406 -87532182 -87532182 -87532182 -87532182 -87532182 -87532182 -87532182 -76710406…

Example 2:

Input: 1878 -106642457 -639485589 -330635263 -211508897 42747648 202609952 -410485495 -364803360 -305016130 402080236 -850795265 -792068413 736132276 171229294 -256887008 -720647107 834292184 -186587154 -365825527 738726945 -766100779 32523570 778579232 -65420968 -73257651 -400825970 718325975 -703450005 593765101 674066814 466479117 480540027 208783007 828901667 -344229819 -875114527 -706940703 -563785217 -475420703 424664092 306065575 -800863558 695998476 699179560 271021127 768404575 819034879 39551178 -31631602 182701698 -806048137 716450585 -28908246 993024135 -20839728 -941308181 187985275 266101317 71627573 255542104 673826713 -451611166 -220831531 264126501 997769664 -268735244 965133869 -105881994 -359273890 35142181 697258380 635119285 438779453 -456519741 -927470333 -26238573 79225915 …
Output: -106642457 -639485589 -330635263 -330635263 -211508897 -211508897 -211508897 -330635263 -305016130 -305016130 -305016130 -330635263 -305016130 -305016130 -256887008 -305016130 -256887008 -256887008 -256887008 -256887008 -256887008 -256887008 -211508897 -211508897 -186587154 -211508897 -186587154 -211508897 -186587154 -186587154 -106642457 -106642457 -73257651 -73257651 -73257651 -106642457 -106642457 -186587154 -186587154 -186587154 -106642457 -186587154 -106642457 -106642457 -73257651 -73257651 -65420968 -65420968 -31631602 -31631602 -31631602 -31631602 -28908246 -28908246 -20839728 -28908246 -20839728 -20839728 32523570 32523570 39551178 32523570 32523570 32523570 39551178 32523570 39551178 32523570 32523570 32523570 35142181 35142181 39551178 35142181 35142181 32523570 35142181 35142181…

Example 3:

Input: 2026 -416788915 -38000111 -52286542 -870819327 -333413383 33349892 -100682639 -49967139 416504781 977808077 362293710 535760312 768625748 -734472062 -79865424 67285613 837149097 653929010 875964792 -329404324 -705218655 -212376807 53588094 714619109 -753855759 578552612 -73013048 -775456637 673913561 308487626 -289592939 911119135 335298680 792744480 523026797 1750246 -999043137 3568950 847128609 554524535 462238567 350077402 985506125 377997730 -580962240 -332796937 -597507389 68797863 -234308287 35171859 276724860 648477661 662763035 -619206293 914378734 243099280 260113289 648475834 -6150821 728469156 -286762902 -349699049 41744212 717954642 -188092933 -73660796 -185023443 620181854 289541833 245739658 -586834432 -507184716 -223194132 -507177899 27943673 -170209482 881719375 768563512 4…
Output: -416788915 -416788915 -52286542 -416788915 -333413383 -333413383 -100682639 -100682639 -52286542 -52286542 -49967139 -49967139 -38000111 -49967139 -49967139 -49967139 -38000111 -38000111 33349892 -38000111 -38000111 -49967139 -38000111 -38000111 -38000111 -38000111 -38000111 -49967139 -38000111 -38000111 -38000111 -38000111 33349892 33349892 53588094 33349892 33349892 3568950 33349892 33349892 53588094 53588094 67285613 67285613 67285613 53588094 53588094 53588094 53588094 35171859 53588094 53588094 67285613 53588094 67285613 67285613 68797863 68797863 68797863 68797863 68797863 67285613 67285613 67285613 67285613 53588094 53588094 53588094 67285613 67285613 67285613 53588094 53588094 41744212 41744212 35171859 41744212 41744212 53588094 41744212 41744212 35171859 35171859 33349892 3517185…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The marks at Masthead - MEDIUM Coding Problem | CodeTikki