CT63555

The Wistful Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the steppe camp of Horselord Plains, someone must map a faster supply route. This year the task falls to Ysolde, armed only with the signals 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: 2615 -924507405 537769500 -446444298 523796917 919931264 -567555072 740946369 -827093079 959470752 -304405188 56674830 888305614 -420672786 -453642803 -588300505 -733899810 -711156053 -400075713 -791254289 679708905 935993167 -602065195 -994319199 -433052803 -137567466 -337297558 -310732213 -581686475 940905304 -816170849 866675931 -520090545 352056431 -735896949 298004068 346605023 -992217323 479453840 -42762267 517506402 393632676 912518983 607513807 855652522 684864471 -320672273 619652952 -801288748 -78973363 -328614105 606656757 608039289 -133175788 -711542403 837320337 552263464 72463428 -354116794 147327304 -675032287 -727057412 -663756933 797494743 -518084757 -449555493 -870000266 336811806 40317973 -655898980 104434280 -443697536 948751976 489186910 683985132 -551285642 918254190 …
Output: -924507405 -924507405 -446444298 -446444298 523796917 -446444298 523796917 -446444298 523796917 -304405188 56674830 56674830 56674830 -304405188 -304405188 -420672786 -420672786 -420672786 -420672786 -420672786 -400075713 -420672786 -420672786 -433052803 -420672786 -420672786 -400075713 -420672786 -400075713 -420672786 -400075713 -420672786 -400075713 -420672786 -400075713 -400075713 -400075713 -400075713 -337297558 -337297558 -310732213 -310732213 -304405188 -304405188 -137567466 -304405188 -137567466 -304405188 -137567466 -304405188 -137567466 -137567466 -133175788 -137567466 -133175788 -133175788 -78973363 -133175788 -78973363 -133175788 -133175788 -137567466 -133175788 -137567466 -137567466 -304405188 -137567466 -137567466 -137567466 -137567466 -137567466 -137567466 -133175788 -1331757…

Example 2:

Input: 127 104280486 551611271 -259687024 409481508 910866358 -576999424 -349784304 -648268854 -145520310 675926383 781440180 -708546473 681700567 -344471405 -287655222 195453253 783473042 330978191 -221325643 -993131420 -105011593 -219955936 -839912370 27337564 -801673983 -541209239 679793409 -904539994 908208013 -239092200 -437879908 567688434 -648216748 384070669 421377481 -845525193 127302850 612048344 136028048 656810643 518796975 9091950 492121752 525437934 -792459773 -431274382 -729446737 947885173 -524924614 -391952143 985489668 110798331 -901878726 -941390187 190487794 46181421 722757510 -778102048 895799867 216456687 -717351982 846861325 -633974384 734634403 568469411 -136438417 203216292 -915492154 222131909 -302249218 -375552597 242527100 981883453 -242509000 556834096 337874771 -8915…
Output: 104280486 104280486 104280486 104280486 409481508 104280486 104280486 -259687024 -145520310 -145520310 104280486 -145520310 104280486 -145520310 -145520310 -145520310 104280486 104280486 104280486 -145520310 -105011593 -145520310 -145520310 -145520310 -145520310 -219955936 -145520310 -219955936 -145520310 -219955936 -219955936 -219955936 -219955936 -219955936 -145520310 -219955936 -145520310 -145520310 -105011593 -105011593 27337564 9091950 27337564 27337564 27337564 9091950 9091950 9091950 9091950 -105011593 9091950 9091950 9091950 -105011593 9091950 9091950 27337564 9091950 27337564 27337564 27337564 27337564 27337564 27337564 46181421 27337564 46181421 27337564 46181421 27337564 27337564 27337564 46181421 27337564 46181421 46181421 46181421 27337564 27337564 15837620 27337564 15837620 1…

Example 3:

Input: 2703 -851428357 68192909 434202101 614790523 -902673583 452384033 602524762 307054763 879816423 55943157 -183903228 -828773311 396523374 -833801141 -314012837 -26628499 -765461796 792279421 211826408 196629198 -383627052 -68057385 -464353711 -995156522 -228500882 -506461621 296423854 -133011877 599210145 -213975745 -465263174 -413204455 34173470 -72333370 -481947965 -780348030 -865321252 -57344100 -879711118 -184630922 -537706488 135634157 -434002490 -505284662 442009793 414240423 475252391 -810517847 -924658500 120141905 -399852830 -565938597 -759391707 443460469 -593982179 867307588 346569799 480909640 705014095 -95969077 -638444745 632195931 -919964169 856498252 447897570 188027127 905274242 560995568 635291944 -982065064 567994075 -885306290 -851164235 21431488 -736739616 -946863743 53…
Output: -851428357 -851428357 68192909 68192909 68192909 68192909 434202101 307054763 434202101 307054763 307054763 68192909 307054763 68192909 68192909 55943157 55943157 55943157 68192909 68192909 68192909 55943157 55943157 -26628499 -26628499 -68057385 -26628499 -68057385 -26628499 -68057385 -68057385 -133011877 -68057385 -72333370 -72333370 -133011877 -133011877 -133011877 -133011877 -183903228 -183903228 -183903228 -183903228 -184630922 -183903228 -183903228 -133011877 -183903228 -183903228 -183903228 -183903228 -184630922 -184630922 -184630922 -184630922 -184630922 -183903228 -183903228 -133011877 -133011877 -133011877 -133011877 -133011877 -133011877 -95969077 -95969077 -72333370 -72333370 -68057385 -72333370 -68057385 -72333370 -72333370 -72333370 -72333370 -95969077 -72333370 -72333370 -72…

Constraints:

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

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