CT58502

The Vermilion Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the old quarter of Brasshaven as Freya unrolls the day's manifest of ledgers. The tally will decide the next shipment. 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: 1782 -291880399 537650242 104298330 -294934798 -77055969 659517223 281118570 303415520 -114278339 -609550780 419787911 -947875077 631931442 892866868 -515122867 903607263 89714646 -544249578 -314757527 -22435863 891269106 -971330005 972434740 -404845844 218807051 -101038915 -579335802 656955967 -399442019 660809593 -140902886 246754089 -77046447 67609876 -880109811 849784582 692484913 -272058586 -164550289 363055675 -415332335 -595549562 28433492 710883918 -114094403 -333927670 337814828 -732223409 921921963 -952711166 359817587 -907751402 365568902 891522501 -619410318 304474677 -749148677 -479194317 910807923 -207350069 -63542998 -119054412 56664171 93645286 267795997 -287092059 -8490579 -820652128 905889241 698689579 -321909739 -37251866 647910866 841515876 -275732029 672535861 18933774…
Output: -291880399 -291880399 104298330 -291880399 -77055969 -77055969 104298330 104298330 104298330 -77055969 104298330 -77055969 104298330 104298330 104298330 104298330 104298330 89714646 89714646 -22435863 89714646 -22435863 89714646 -22435863 89714646 -22435863 -22435863 -22435863 -22435863 -22435863 -22435863 -22435863 -22435863 -22435863 -22435863 -22435863 67609876 -22435863 -22435863 -22435863 -22435863 -77046447 -22435863 -22435863 -22435863 -77046447 -22435863 -77046447 -22435863 -77046447 -22435863 -77046447 -22435863 -22435863 -22435863 -22435863 -22435863 -77046447 -22435863 -77046447 -63542998 -77046447 -63542998 -63542998 -22435863 -63542998 -22435863 -63542998 -22435863 -22435863 -22435863 -37251866 -22435863 -22435863 -22435863 -22435863 -8490579 -22435863 -22435863 -22435863 -224…

Example 2:

Input: 3649 -118702589 -950188721 -792023590 99946224 97932563 -288593844 -440535721 320557624 -264490673 55360936 942488650 247799265 -608810891 -659527488 142302467 674432950 -772028416 -632551895 -502743773 166610500 751319637 -117562824 -862479510 170706473 -517715840 -715461862 774394669 990811735 749564616 122619919 859152458 -944975097 970106001 -195380987 334536465 2447438 442405107 -935390492 -630824541 555141316 -900114707 163982951 737201278 868228462 267950745 345329131 424239643 377855324 123750952 -413585386 11853494 -968999276 18840703 158683131 462653832 928519266 -175621624 160241102 613719537 -592722887 445496959 -579651167 33613006 -515553962 -116121547 557574322 -936515718 -208212624 193325667 152707976 -724649550 36007172 -841162778 -787540282 630963231 -532125943 -174425361 …
Output: -118702589 -950188721 -792023590 -792023590 -118702589 -288593844 -288593844 -288593844 -264490673 -264490673 -118702589 -118702589 -118702589 -264490673 -118702589 -118702589 -118702589 -264490673 -264490673 -264490673 -118702589 -118702589 -118702589 -118702589 -118702589 -264490673 -118702589 -118702589 -117562824 -117562824 55360936 -117562824 55360936 -117562824 55360936 2447438 55360936 2447438 2447438 2447438 2447438 2447438 55360936 55360936 97932563 97932563 99946224 99946224 122619919 99946224 99946224 97932563 97932563 97932563 99946224 99946224 99946224 99946224 122619919 99946224 122619919 99946224 99946224 97932563 97932563 97932563 97932563 55360936 97932563 97932563 97932563 55360936 55360936 36007172 55360936 36007172 36007172 33613006 33613006 33613006 36007172 33613006 3…

Example 3:

Input: 58 -847916894 597070151 -299859668 201817379 561831482 315146768 -811174970 202579222 -981156231 -936966800 -818461315 -853669220 -105633283 660757840 517324980 -692723235 -105368382 -275964330 -294855589 -127677095 -528938930 -148688373 -406387888 -350241853 158048935 583514055 635408082 -248946243 297960739 -875988573 -871036622 148631593 845076840 -792842180 -485163825 -254403077 -343370088 425455569 -644186792 -861937580 -97814224 -960504494 786123485 596270864 -194344400 16615244 816296204 -591612202 -963464955 528891231 -239105159 980695588 -687041250 -749126954 521849666 -815348875 343414766 -200273804
Output: -847916894 -847916894 -299859668 -299859668 201817379 201817379 201817379 201817379 201817379 -299859668 -299859668 -811174970 -299859668 -299859668 -105633283 -299859668 -105633283 -275964330 -275964330 -275964330 -275964330 -275964330 -275964330 -294855589 -275964330 -275964330 -148688373 -248946243 -148688373 -248946243 -248946243 -248946243 -148688373 -248946243 -248946243 -254403077 -254403077 -254403077 -254403077 -275964330 -254403077 -275964330 -254403077 -254403077 -248946243 -248946243 -194344400 -248946243 -248946243 -248946243 -239105159 -239105159 -239105159 -248946243 -239105159 -248946243 -239105159 -239105159

Constraints:

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

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