CT60948

Ravi and the Vermilion ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Ravi found an old ledger of ledgers in the archive attic at the copper works of Verdigris. The margin notes pose a precise question. 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: 3590 467840789 173425277 505793490 675925988 -987899047 991994779 -956823555 -723162596 803817536 859812779 428104756 -723978578 831374334 -30780058 51714814 460498195 -609075810 53235338 714371697 608522248 658927236 450099154 -753596929 -658996123 159006816 -832759965 -407359189 240262110 -472983770 953217869 -957621172 -415664244 258181500 -871740419 59056994 -533031428 -669306362 792934671 -71298727 -211508733 308001864 231989015 901621149 -838289355 -996381350 750689417 -270092039 619985380 -338965138 -418043673 -2280561 -301367108 632016476 -211251052 -193754721 744627404 -93081291 -818376532 -576730840 584571597 -617089150 -226193191 916859346 -335695700 -726144166 -488073656 997650036 -971861162 -840316159 319262092 332021523 630822398 41410419 626144489 -137649016 -373461363 18645…
Output: 467840789 173425277 467840789 467840789 467840789 467840789 467840789 173425277 467840789 467840789 467840789 428104756 467840789 428104756 428104756 428104756 428104756 173425277 428104756 428104756 460498195 450099154 450099154 428104756 428104756 173425277 173425277 173425277 173425277 173425277 173425277 159006816 173425277 159006816 159006816 59056994 59056994 59056994 59056994 53235338 59056994 59056994 159006816 59056994 59056994 59056994 59056994 59056994 59056994 53235338 53235338 51714814 53235338 51714814 51714814 51714814 51714814 -2280561 -2280561 -2280561 -2280561 -30780058 -2280561 -30780058 -30780058 -71298727 -30780058 -71298727 -71298727 -71298727 -30780058 -30780058 -2280561 -2280561 -2280561 -30780058 -2280561 -30780058 -30780058 -30780058 -4685713 -30780058 -30780058 -…

Example 2:

Input: 2831 -119160657 978806271 -79347505 -137843207 -647570410 293190124 68292285 62743609 862850086 481187648 -938109775 920024550 726684244 -246140039 924380795 -925214098 629179894 -260355459 -374448847 -448455639 -241252636 5783413 -386519083 -93256829 -556549705 -422357956 284687106 -614988145 -345058736 435533522 777693068 -38691240 782404530 742262233 336204486 958388191 -634251725 -176851111 -327282709 -836695664 -450797825 244587250 964052840 -799190764 -309023200 225182590 -195303509 -19848043 -760911476 -809419798 477578730 85370119 753127524 -396271915 -720852742 -147991142 591847675 862189549 442918533 -800743098 -853891523 -546255805 -216948495 -964794307 85841729 494165110 34837960 720550483 61301603 -540932639 -142199160 114289646 -891272945 252080523 802736142 929683788 -429804…
Output: -119160657 -119160657 -79347505 -119160657 -119160657 -119160657 -79347505 -79347505 62743609 62743609 62743609 62743609 68292285 62743609 68292285 62743609 68292285 62743609 62743609 -79347505 -79347505 -79347505 -79347505 -93256829 -93256829 -119160657 -93256829 -119160657 -119160657 -119160657 -93256829 -93256829 -79347505 -79347505 -38691240 -38691240 -38691240 -79347505 -79347505 -93256829 -93256829 -93256829 -79347505 -93256829 -93256829 -93256829 -93256829 -93256829 -93256829 -119160657 -93256829 -93256829 -79347505 -93256829 -93256829 -119160657 -93256829 -93256829 -79347505 -93256829 -93256829 -119160657 -119160657 -137843207 -119160657 -119160657 -93256829 -93256829 -79347505 -93256829 -93256829 -93256829 -93256829 -93256829 -79347505 -79347505 -79347505 -79347505 -79347505 -9325…

Example 3:

Input: 2908 -236834385 -565483838 -329967107 -996907658 -296769188 596224036 -248040245 795237766 733607125 -972365990 967089201 563193019 -406523422 128122515 -539805286 879847776 862358345 94581746 386292815 -916895451 -804738219 -916015691 -384205557 -983038727 -464334177 234697369 -707350511 -776913638 -984047305 -819699465 -877827440 955905454 157932140 35827473 -661885254 165606666 -512860831 -482511141 -485134179 -982763273 -706015622 259459339 -21856544 682582321 248273597 -477918325 898051016 267013996 -793650696 727905574 -99492566 -40263923 113022544 -445858683 409906506 -259861009 -68776113 243494013 465113913 -877014150 -449025232 62182209 -267256405 137506885 -463751936 -268798834 -337530188 799327618 651376916 704723809 -847428286 512009451 -260485687 567317323 -818300021 -56150510…
Output: -236834385 -565483838 -329967107 -565483838 -329967107 -329967107 -296769188 -296769188 -248040245 -296769188 -248040245 -248040245 -248040245 -248040245 -248040245 -248040245 -236834385 -236834385 94581746 -236834385 -236834385 -248040245 -248040245 -296769188 -296769188 -296769188 -296769188 -329967107 -329967107 -384205557 -384205557 -384205557 -329967107 -329967107 -329967107 -329967107 -329967107 -384205557 -384205557 -406523422 -406523422 -406523422 -384205557 -384205557 -329967107 -384205557 -329967107 -329967107 -329967107 -329967107 -296769188 -296769188 -248040245 -296769188 -248040245 -259861009 -248040245 -248040245 -236834385 -248040245 -248040245 -248040245 -248040245 -248040245 -248040245 -259861009 -259861009 -259861009 -248040245 -248040245 -248040245 -248040245 -248040245…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Ravi and the Vermilion ledgers - MEDIUM Coding Problem | CodeTikki