CT62515

The Middle So Far of Rainhaven

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Wade the paymaster watches over the monsoon port of Rainhaven's stores of signals. A careful computation stands between order and chaos. 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: 3998 489763125 -450762550 412633656 -80609666 -774154408 455093193 -729578220 -534473592 -674642830 -725319759 -800883032 58489727 271139921 -311386979 -949552774 -989863761 164732602 740235156 -91486662 -386385909 -132964949 932528092 -2565513 849316795 -930751753 607550676 -537567017 -630397226 159203751 -819119114 -649058435 503724222 -888166714 432704198 -504743548 -944395941 -201618814 601461216 -726032524 803433515 -971001480 -350397411 388575682 -893216746 917498102 536192467 -722815573 -530677584 -131495916 -760442477 144507659 730564536 23035335 794853848 -860874344 -25805609 -785693592 -837736671 201950157 -885189652 410365067 -56529746 -431742864 -346820964 524217349 -943541130 -327935872 263332488 894972 19257048 -970171435 -39589368 141849041 -641737339 623022342 286401346 -33…
Output: 489763125 -450762550 412633656 -80609666 -80609666 -80609666 -80609666 -450762550 -450762550 -534473592 -534473592 -534473592 -450762550 -450762550 -450762550 -534473592 -450762550 -450762550 -311386979 -386385909 -311386979 -311386979 -132964949 -132964949 -132964949 -132964949 -132964949 -311386979 -132964949 -311386979 -311386979 -311386979 -311386979 -311386979 -311386979 -386385909 -311386979 -311386979 -311386979 -311386979 -311386979 -350397411 -311386979 -350397411 -311386979 -311386979 -311386979 -350397411 -311386979 -350397411 -311386979 -311386979 -201618814 -201618814 -201618814 -201618814 -201618814 -311386979 -201618814 -311386979 -201618814 -201618814 -201618814 -311386979 -201618814 -311386979 -311386979 -311386979 -201618814 -201618814 -201618814 -201618814 -132964949 -20…

Example 2:

Input: 1546 -336161786 248144624 -229775135 -528156295 67154776 -218804858 605280078 -951453396 567259757 -167562040 196028192 270422120 -312504973 25271 203881138 -563454201 -24400951 897346187 159294227 907575622 452850744 -292947499 165530785 523180739 441237202 807706576 -110016849 618500588 -330088198 37898455 346023884 821311173 -219900250 345774447 976329696 423844127 316056015 -118438609 299596517 -381685403 395040080 915594323 -716862164 -973503273 611464632 -798726955 161362698 -207647925 -578470645 -155963589 -174326578 -724529494 -119701825 440780838 175428441 -773537943 -136485023 -416542955 782542560 939941294 129869457 -306690977 -398695206 -136584137 -744322554 -412368078 -891046595 563919030 564306192 495162998 901488833 575406822 -347955640 -182494022 582255211 713154117 5777437…
Output: -336161786 -336161786 -229775135 -336161786 -229775135 -229775135 -218804858 -229775135 -218804858 -218804858 -167562040 -167562040 -167562040 -167562040 25271 -167562040 -24400951 -24400951 25271 25271 67154776 25271 67154776 67154776 159294227 159294227 159294227 159294227 159294227 67154776 159294227 159294227 159294227 159294227 165530785 165530785 196028192 165530785 196028192 165530785 196028192 196028192 196028192 165530785 196028192 165530785 165530785 161362698 161362698 159294227 159294227 67154776 67154776 67154776 159294227 67154776 67154776 37898455 67154776 67154776 129869457 67154776 67154776 37898455 37898455 25271 25271 25271 37898455 37898455 67154776 67154776 67154776 37898455 67154776 67154776 129869457 129869457 159294227 159294227 161362698 159294227 159294227 1298694…

Example 3:

Input: 1019 364296875 680941772 62019351 562924026 371131848 211062970 -383472315 -610255268 -112834225 993066991 264548505 972439924 502175957 -225536601 415729439 -177494639 738465780 345673750 -449554362 -208320498 354664188 41364010 215107064 -437582961 427499361 343155949 773426009 -816017920 439655494 742968758 -231483039 -539845326 -364004854 425831465 52092825 -859399039 -140127196 926327473 -536465735 -868833320 -123624852 483108993 157841936 -838605724 -210233110 -608749236 -828364767 -272063068 -571978832 777464432 238389027 -535633857 223688705 534037219 -397642123 46841007 655904754 -611841197 212204580 304636780 -930844772 -22992391 828475611 999764954 -374685177 -287419653 683068382 550698345 -69457154 -184629110 -250194106 464698686 -761626395 968989417 397536745 -958834493 241285…
Output: 364296875 364296875 364296875 364296875 371131848 364296875 364296875 211062970 211062970 211062970 264548505 264548505 364296875 264548505 364296875 264548505 364296875 345673750 345673750 264548505 345673750 264548505 264548505 215107064 264548505 264548505 343155949 264548505 343155949 343155949 343155949 264548505 264548505 264548505 264548505 215107064 215107064 215107064 215107064 211062970 211062970 211062970 211062970 157841936 157841936 62019351 62019351 52092825 52092825 52092825 62019351 52092825 62019351 62019351 62019351 52092825 62019351 52092825 62019351 62019351 62019351 52092825 62019351 62019351 62019351 52092825 62019351 62019351 62019351 52092825 52092825 52092825 52092825 52092825 62019351 52092825 62019351 62019351 62019351 62019351 62019351 52092825 62019351 62019351…

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