CT58708

The Middle So Far Beneath Deepwater

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the fjord village of Deepwater with crates of ledgers, and Kate the store warden must account for every last one. 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: 3975 977706121 -210020744 -88735586 877310488 717507974 -261998489 -672358001 472808383 -378268943 749283996 -522203686 7316739 -275734302 -676352817 -984396812 524937866 -253622229 -266721746 -582894303 535189091 426552878 318522321 -889540034 -479945102 -534939677 -529838667 929184330 168342831 -771608033 60179476 -889305762 -136476462 558480199 -831984185 -681495973 556363360 -225808874 42696343 -999683219 738974781 908054658 -55247848 411518977 712130869 -994430202 -500386122 509089512 627066706 -945931708 149146189 -682130994 -622643610 984988923 -532048538 -562238719 415290774 -821671120 15861078 -913367707 759496445 215084667 -174564666 -779724832 737722289 -586562798 693753132 870132116 227031305 -130571808 347721417 858333873 -30739635 814648203 972392230 361275950 294287237 17711…
Output: 977706121 -210020744 -88735586 -88735586 717507974 -88735586 -88735586 -88735586 -88735586 -88735586 -88735586 -88735586 -88735586 -210020744 -210020744 -210020744 -210020744 -253622229 -253622229 -253622229 -210020744 -210020744 -210020744 -253622229 -253622229 -261998489 -253622229 -253622229 -253622229 -253622229 -253622229 -253622229 -210020744 -253622229 -253622229 -253622229 -225808874 -225808874 -225808874 -225808874 -210020744 -210020744 -136476462 -136476462 -136476462 -210020744 -136476462 -136476462 -136476462 -136476462 -136476462 -210020744 -136476462 -210020744 -210020744 -210020744 -210020744 -210020744 -210020744 -210020744 -136476462 -174564666 -174564666 -174564666 -174564666 -174564666 -136476462 -136476462 -130571808 -130571808 -88735586 -88735586 -55247848 -55247848 -3…

Example 2:

Input: 1289 365491821 444598179 -672345761 -373315400 581319377 -658601868 261697725 688509639 988663650 522619962 722193952 327172588 -65929309 -955595443 863982190 -414054599 228313674 980491593 -143862364 206723250 -804365584 381884819 533361875 434286835 96957457 180612166 999711041 -872552891 979619424 -535027091 -207249273 55551739 -465727625 646262210 538531399 -463978083 -760468652 21755512 -89939096 -441052399 -964697751 -152007341 591291260 -647636634 645869994 927458744 495521923 -673409143 335772108 817204316 431828722 801808053 -129892487 905608567 654439976 -543918816 456469579 611295675 -850798241 -614400213 667184259 470295832 -668426725 835821977 609865904 -147566989 -473838174 485198487 -468486764 -445541655 -954820739 302675249 144196492 460814351 -994682373 -842254834 -8294520…
Output: 365491821 365491821 365491821 -373315400 365491821 -373315400 261697725 261697725 365491821 365491821 444598179 365491821 365491821 327172588 365491821 327172588 327172588 327172588 327172588 261697725 261697725 261697725 327172588 327172588 327172588 261697725 327172588 261697725 327172588 261697725 261697725 228313674 228313674 228313674 261697725 228313674 228313674 206723250 206723250 180612166 180612166 96957457 180612166 96957457 180612166 180612166 206723250 180612166 206723250 206723250 228313674 228313674 228313674 228313674 261697725 228313674 261697725 261697725 261697725 228313674 261697725 261697725 261697725 261697725 327172588 261697725 261697725 261697725 261697725 228313674 228313674 228313674 228313674 228313674 228313674 206723250 206723250 206723250 206723250 206723250 …

Example 3:

Input: 1879 -32197617 -857290929 921273595 -383315213 581098414 -224089937 -182390006 -758125256 -27944996 -883909223 255545261 609750554 780909137 -208175300 734320429 73208780 614408822 -159707582 -705283948 139733684 -996252409 -423501793 754313804 -318827458 491915769 331663562 -843873205 82788479 460308723 955387200 235840589 -339839237 302120539 856078434 -89264346 -83059212 228051735 -474114052 38618111 -807337071 167293468 36985493 -71949959 -291344993 -146866852 -72466691 279548082 527778864 671744249 -851458628 208308771 -605429234 -566232247 -912524826 -339617041 140486737 -408961065 -963871285 -491432202 -584978808 705078045 -751241432 -643486491 739409477 -690837117 -825198685 -528170385 885968117 964598666 -614693936 678674126 811584676 48948789 -357171460 166451923 -598515620 48821…
Output: -32197617 -857290929 -32197617 -383315213 -32197617 -224089937 -182390006 -224089937 -182390006 -224089937 -182390006 -182390006 -32197617 -182390006 -32197617 -32197617 -27944996 -32197617 -32197617 -32197617 -32197617 -159707582 -32197617 -159707582 -32197617 -32197617 -32197617 -32197617 -27944996 -27944996 73208780 -27944996 73208780 73208780 73208780 -27944996 73208780 -27944996 38618111 -27944996 38618111 36985493 36985493 -27944996 -27944996 -32197617 -27944996 -27944996 36985493 -27944996 36985493 -27944996 -27944996 -32197617 -32197617 -32197617 -32197617 -71949959 -71949959 -72466691 -71949959 -72466691 -72466691 -72466691 -72466691 -83059212 -83059212 -83059212 -72466691 -83059212 -72466691 -72466691 -71949959 -72466691 -71949959 -72466691 -71949959 -71949959 -71949959 -72466691…

Constraints:

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

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