CT58239

The Middle So Far of Caravanrest

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the dune sea of Caravanrest opens only for a perfect tally of beacons. Iker 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: 2627 477281705 863016437 214459341 -606285436 719434896 700408358 419670634 132725869 800813570 -763773457 203613853 494602097 494088332 -302519179 44230921 -706608157 -148020372 812834313 -308699207 184917695 330392203 -358561317 -713282427 799531096 781200857 -834835218 -215507935 618701958 -158978885 581015028 -868784241 74330139 375594815 210818072 674600178 -874707672 726376935 850426359 563671133 -379739615 -491620471 744995781 -89743679 984060620 -749180359 623910776 -534608302 -44767701 -985873872 972959817 -375480833 248121644 627933010 289134973 757848053 502533217 491073937 525900380 -197554569 -867551077 -673040052 -873220744 -421092620 269487375 -810949977 -684807689 -528550147 518188764 -971654137 655037264 -338298955 -528869143 -93690362 116344169 -66621431 -214803850 -56063…
Output: 477281705 477281705 477281705 214459341 477281705 477281705 477281705 419670634 477281705 419670634 419670634 419670634 477281705 419670634 419670634 214459341 214459341 214459341 214459341 203613853 214459341 203613853 203613853 203613853 214459341 203613853 203613853 203613853 203613853 203613853 203613853 184917695 203613853 203613853 210818072 203613853 210818072 210818072 214459341 210818072 210818072 210818072 210818072 210818072 210818072 210818072 210818072 203613853 203613853 203613853 203613853 203613853 210818072 210818072 214459341 214459341 248121644 248121644 248121644 214459341 214459341 210818072 210818072 210818072 210818072 203613853 203613853 203613853 203613853 203613853 203613853 184917695 184917695 132725869 132725869 116344169 116344169 74330139 116344169 116344169 1…

Example 2:

Input: 2855 388384704 562905078 29699835 -811112917 -213207960 202526467 -217697441 -264296721 -714143421 -425247084 -649939210 -530432940 -920965440 -443503022 -196096712 889829748 849093345 654489267 -412851242 522946209 279801808 -765639416 521964602 -886085624 -182348582 -142068335 -994976712 158734445 32542587 -98508953 -691383289 575708471 -331274921 636075716 498703969 -45734163 43484008 -253909193 577570833 58211337 -478263584 684277834 -981692607 88983864 -107815653 -490819853 -853395055 526334516 960559205 250784418 -464764742 -888688929 -500885566 -868183078 -581781306 971957838 298467685 9641559 123432295 848009107 935820571 -388174171 -47269681 -511262637 -603313716 631083573 941243518 450030936 -44097476 672260209 -990996494 -134480292 -302208323 -28174256 268664046 949268437 -70187…
Output: 388384704 388384704 388384704 29699835 29699835 29699835 29699835 -213207960 -213207960 -217697441 -217697441 -264296721 -264296721 -425247084 -264296721 -264296721 -217697441 -217697441 -217697441 -217697441 -213207960 -217697441 -213207960 -217697441 -213207960 -213207960 -213207960 -213207960 -196096712 -196096712 -196096712 -196096712 -196096712 -196096712 -182348582 -182348582 -142068335 -182348582 -142068335 -142068335 -142068335 -142068335 -142068335 -142068335 -107815653 -142068335 -142068335 -142068335 -107815653 -107815653 -107815653 -142068335 -142068335 -182348582 -182348582 -182348582 -142068335 -142068335 -107815653 -107815653 -98508953 -107815653 -98508953 -107815653 -107815653 -107815653 -98508953 -98508953 -47269681 -47269681 -47269681 -98508953 -98508953 -98508953 -472696…

Example 3:

Input: 3045 -694080439 -666134161 -534138727 -543187028 33688154 831586559 699038292 -578524802 485755668 373607858 522222347 246349940 -403159935 169926188 -793035885 -97735262 -741423283 182556175 113635445 -88778028 260137515 676875037 587710375 -395966248 789026902 953887564 -300727945 414224334 167098765 209396215 348379249 377680769 -45199341 -369887321 979566234 -700999341 861420804 -151548927 -807300503 660282045 -252751425 814331988 -846427056 -53427803 111447508 230784472 -359752496 -729637998 -685571340 -330166654 322004801 217329835 541784790 547977359 -597061280 -859313255 783607466 -385587944 -623986171 207894196 936704027 -128668885 -742213225 770262915 573834019 943811334 -606591925 -165413499 614067643 -753617752 -834668600 554489084 -178167819 817135788 444570761 510031291 -4771…
Output: -694080439 -694080439 -666134161 -666134161 -543187028 -543187028 -534138727 -543187028 -534138727 -534138727 33688154 33688154 33688154 33688154 33688154 -97735262 -97735262 -97735262 33688154 -88778028 33688154 33688154 113635445 33688154 113635445 113635445 113635445 113635445 167098765 167098765 169926188 169926188 169926188 167098765 169926188 167098765 169926188 167098765 167098765 167098765 167098765 167098765 167098765 113635445 113635445 113635445 113635445 111447508 111447508 33688154 111447508 111447508 113635445 113635445 113635445 111447508 113635445 111447508 111447508 111447508 113635445 111447508 111447508 111447508 113635445 113635445 113635445 111447508 113635445 111447508 111447508 111447508 111447508 111447508 113635445 113635445 113635445 111447508 113635445 113635445 …

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 Caravanrest - MEDIUM Coding Problem | CodeTikki