CT59228

The Middle So Far of Redrock

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the canyon post of Redrock, someone must plan the harvest festival. This year the task falls to Quill, armed only with the beacons register. 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: 684 -887196726 132765838 906393523 734290815 -401866362 -931300151 -708454543 -41334734 742389539 -203559474 -595738992 -735264312 -691252025 175818504 399413638 -310446060 -473120355 -355318113 170619422 -217600732 -594905441 -836495753 -190885063 -97051363 154088838 -171802564 -74360813 -637090852 -113794620 -694099228 253138547 -256864350 -324379182 -806601230 -554923353 302311084 -367167525 -950180626 -128116364 -503816783 90705217 495983887 444412186 -686046518 -193088082 774999305 733247615 -571827883 -408414176 555572868 439620954 -517136979 618747852 -933447796 -57911690 771937617 -62410032 -416053638 -497431577 -575415298 537798718 194434309 989379199 -650667513 567367903 18951349 312901226 -48639943 -886933899 717269064 -371372921 518613785 -14068686 242279918 968092541 -69200457…
Output: -887196726 -887196726 132765838 132765838 132765838 -401866362 -401866362 -401866362 -41334734 -203559474 -203559474 -401866362 -401866362 -401866362 -203559474 -310446060 -310446060 -355318113 -310446060 -310446060 -310446060 -355318113 -310446060 -310446060 -217600732 -217600732 -203559474 -217600732 -203559474 -217600732 -203559474 -217600732 -217600732 -256864350 -256864350 -256864350 -256864350 -310446060 -256864350 -310446060 -256864350 -256864350 -217600732 -256864350 -217600732 -217600732 -203559474 -217600732 -217600732 -217600732 -203559474 -217600732 -203559474 -217600732 -203559474 -203559474 -193088082 -203559474 -203559474 -217600732 -203559474 -203559474 -193088082 -203559474 -193088082 -193088082 -190885063 -190885063 -190885063 -190885063 -190885063 -190885063 -171802564 -…

Example 2:

Input: 445 -736671230 -543749209 346454289 150546973 426987231 580625304 527628959 -34909466 -643677040 181617783 -659084964 -197738402 -106496313 160648448 -853868607 598779083 936357789 166022455 -709907937 468178228 102936388 362575971 -778656446 -210679158 -915594765 289400759 -892237133 -770921500 470664556 801957125 -193822663 71804442 -266062542 710726914 621119830 -697466639 824186044 -862665303 949532948 -114406708 245006051 -138589717 808880669 72907176 -117981904 555988846 -746678727 -157411280 -734408683 -689329417 -70419746 -162210946 -538206085 -237042573 426137584 699834315 102367270 997678732 445845790 -137772688 -784095992 -757704224 -735319716 40792056 807771351 529650274 -297715396 430708197 428480737 76152044 726105723 -444630564 -521700670 901987894 -471751933 854114970 26480…
Output: -736671230 -736671230 -543749209 -543749209 150546973 150546973 346454289 150546973 150546973 150546973 150546973 -34909466 -34909466 -34909466 -34909466 -34909466 150546973 150546973 150546973 150546973 150546973 150546973 150546973 102936388 102936388 102936388 102936388 -34909466 102936388 102936388 102936388 71804442 71804442 71804442 102936388 71804442 102936388 71804442 102936388 71804442 102936388 71804442 102936388 72907176 72907176 72907176 72907176 71804442 71804442 -34909466 -34909466 -70419746 -70419746 -106496313 -70419746 -70419746 -34909466 -34909466 71804442 -34909466 -34909466 -70419746 -70419746 -70419746 -34909466 -34909466 -34909466 -34909466 40792056 40792056 71804442 40792056 40792056 40792056 40792056 40792056 71804442 71804442 72907176 71804442 72907176 71804442 718…

Example 3:

Input: 1812 -963126103 442537853 -710743047 -116243508 566309675 -463688309 218098186 -133572054 633928383 303354647 -165813876 828886497 958143694 -206419404 494514376 -856462507 482210349 -806067365 651870514 -729164400 759304138 -704594168 -961363384 413802176 319389 -1533572 693470107 -353845755 -609170019 170451559 619126065 461124877 -619641342 -204050504 529438271 855530623 -386887585 104251814 -988246332 28540855 943378309 -628193887 45563912 36029628 73387066 -713100825 -81155538 193322091 836642916 -426609534 258689794 664000840 -484090916 -585478388 -469142727 379251371 621743395 -296296282 -227846085 -1291972 914893649 474475961 254016854 147253728 -572205564 -238296843 233925866 858726796 -595485962 436063877 -126617103 312234873 -774798466 431783854 -459555819 602301315 -668098348 9…
Output: -963126103 -963126103 -710743047 -710743047 -116243508 -463688309 -116243508 -133572054 -116243508 -116243508 -116243508 -116243508 218098186 -116243508 218098186 -116243508 218098186 -116243508 218098186 -116243508 218098186 -116243508 -116243508 -116243508 319389 -1533572 319389 -1533572 -1533572 -1533572 319389 319389 319389 -1533572 319389 319389 319389 319389 319389 319389 28540855 319389 28540855 28540855 36029628 28540855 28540855 28540855 36029628 28540855 36029628 36029628 36029628 28540855 28540855 28540855 36029628 28540855 28540855 319389 28540855 28540855 36029628 36029628 36029628 28540855 36029628 36029628 36029628 36029628 36029628 36029628 36029628 36029628 36029628 36029628 36029628 36029628 36029628 28540855 36029628 36029628 36029628 36029628 36029628 36029628 36029628 …

Constraints:

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

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