CT61840

Ivan's registers Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Ivan inherited the apiary at the river town of Willowford along with its curious bookkeeping system for registers. Time to make sense of it. 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: 2198 57611417 -419858713 247004715 -292726868 -996371885 682067239 145265540 -690312100 402699894 839266887 -542673972 -618715017 -210973081 -372876479 870816053 -583963317 516851483 -965918362 243515057 -264346373 461342128 56515003 -26008813 149199690 -560478144 549448790 933879686 -408740209 863134432 -819460133 -493946708 908821571 -587730934 389043680 190114458 465527065 114063575 -790511473 -220489514 487368135 -687069130 -674022956 845867817 -404002520 25328989 -452241709 -935190607 -991838727 98158498 606417005 -250891381 443346941 661783185 807446310 362290045 596675018 -388350978 -104165514 -139199750 -101227587 -871630750 -671726209 256578646 777437533 -270515931 741023009 -95379207 -591259348 150109225 6850268 -482881725 482051248 -463680193 652957191 126463111 -92668155 -26025…
Output: 57611417 -419858713 57611417 -292726868 -292726868 -292726868 57611417 -292726868 57611417 57611417 57611417 -292726868 -210973081 -292726868 -210973081 -292726868 -210973081 -292726868 -210973081 -264346373 -210973081 -210973081 -26008813 -26008813 -26008813 -26008813 56515003 -26008813 56515003 -26008813 -26008813 -26008813 -26008813 -26008813 56515003 56515003 57611417 56515003 56515003 56515003 56515003 -26008813 56515003 -26008813 25328989 -26008813 -26008813 -210973081 -26008813 -26008813 -26008813 -26008813 25328989 25328989 56515003 56515003 56515003 25328989 25328989 -26008813 -26008813 -101227587 -26008813 -26008813 -26008813 -26008813 -26008813 -95379207 -26008813 -26008813 -26008813 -26008813 -26008813 -26008813 6850268 -26008813 -26008813 -26008813 6850268 6850268 6850268 6850…

Example 2:

Input: 798 55974614 -457275674 -381507433 672549441 304676137 442160685 -707927894 173984945 -914034428 -781220954 -175721062 -255486125 392964028 -496446980 121999479 767319091 -640824335 905725165 -410479891 202930188 -292855465 -448923685 754877545 -376311162 -938881343 270714593 527097218 -821241335 -833899764 -53042890 -817961401 679885443 802603937 106976462 -224728298 -510034080 297264496 -353195188 216710848 -410801221 -442204681 713457761 -516053122 -720690052 -125597074 -399900323 315102845 362413887 -871113171 -899041786 912572379 284970051 -637076693 -214769079 -952368100 652639867 -654856643 -159380161 -868344703 -647364620 356456000 -633991516 -927496097 761439995 726771945 -842333761 -604688217 456346771 -702192605 -221512518 -385545912 951533553 749432356 -429773999 808901663 9266…
Output: 55974614 -457275674 -381507433 -381507433 55974614 55974614 55974614 55974614 55974614 -381507433 -175721062 -255486125 -175721062 -255486125 -175721062 -175721062 -175721062 -175721062 -175721062 -175721062 -175721062 -255486125 -175721062 -255486125 -255486125 -255486125 -175721062 -255486125 -255486125 -255486125 -255486125 -255486125 -175721062 -175721062 -175721062 -224728298 -175721062 -224728298 -175721062 -224728298 -224728298 -224728298 -224728298 -255486125 -224728298 -255486125 -224728298 -224728298 -224728298 -255486125 -224728298 -224728298 -224728298 -224728298 -224728298 -224728298 -224728298 -224728298 -224728298 -255486125 -224728298 -255486125 -255486125 -255486125 -224728298 -255486125 -255486125 -255486125 -255486125 -255486125 -255486125 -255486125 -224728298 -25548612…

Example 3:

Input: 259 286238808 -950042117 -302230376 -907892662 373279708 171279940 -524092932 132760203 -602322195 986585657 -290103010 -741707008 -396441501 -736634790 840366127 941098662 -43009237 653966695 -76730500 -954018867 -811326068 -550038561 510074864 -192525359 -20418507 787654580 847862443 -92382847 163364208 250528599 68034584 481932088 382813609 997362200 894548736 -29019790 592441866 384979640 462390834 972605102 -470444218 -295515292 209389477 -321977674 739050026 899609610 267795707 289996933 716079478 -242922502 -744735318 -189000464 -773897445 9943911 133020580 -267295882 417647445 91900728 -973569876 912570489 -461641235 594047539 504564653 -798942894 -350176152 854875508 -170657757 883520264 -713920672 786664952 -924539005 410762013 -612686418 162989958 57430726 379672365 -500411614 -…
Output: 286238808 -950042117 -302230376 -907892662 -302230376 -302230376 -302230376 -302230376 -302230376 -302230376 -290103010 -302230376 -302230376 -396441501 -302230376 -302230376 -290103010 -290103010 -76730500 -290103010 -290103010 -302230376 -290103010 -290103010 -192525359 -192525359 -76730500 -92382847 -76730500 -76730500 -43009237 -43009237 -20418507 -20418507 68034584 -20418507 68034584 68034584 132760203 132760203 132760203 68034584 132760203 68034584 132760203 132760203 163364208 163364208 171279940 163364208 163364208 132760203 132760203 68034584 132760203 68034584 132760203 91900728 91900728 91900728 91900728 91900728 132760203 91900728 91900728 91900728 91900728 91900728 91900728 91900728 91900728 91900728 91900728 91900728 91900728 91900728 91900728 68034584 68034584 68034584 91900…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.