CT62766

The Padmore Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The registry keeper Nils has been asked to compute the guild dues owed. On the desk lies a long table of marks readings. 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: 2635 -866830046 -172193177 -534585375 675024903 987572060 -843534813 223510235 123518994 165268630 102651813 -622587984 85968238 -199826911 282437498 657857568 742809572 -732328646 -246521267 -704227037 -627774992 427134854 -194727590 -863061342 -50022936 -176527747 -689247032 -880505897 931428621 63738722 -77368617 -29816484 -944022346 -272282287 -270314646 743825681 957978096 -288274655 376894893 586800232 440296246 822299852 733290959 283109359 -97958503 -931141421 258466715 543842625 -812857331 -703289000 -706392215 -784500974 977468857 902108838 -862378527 -957216784 652704515 -287640076 497292732 710170339 -429665876 942868573 -291522167 593670061 -156966984 -489844539 27378193 -173983211 460947113 143744701 367971661 -602576300 446928250 -878214445 -768139705 626875753 208598994 -10…
Output: -866830046 -866830046 -534585375 -534585375 -172193177 -534585375 -172193177 -172193177 123518994 102651813 102651813 85968238 85968238 85968238 102651813 102651813 102651813 85968238 85968238 -172193177 85968238 -172193177 -172193177 -172193177 -172193177 -176527747 -176527747 -176527747 -172193177 -172193177 -77368617 -172193177 -172193177 -176527747 -172193177 -172193177 -172193177 -172193177 -77368617 -77368617 -50022936 -50022936 -29816484 -50022936 -50022936 -50022936 -29816484 -50022936 -50022936 -77368617 -77368617 -77368617 -50022936 -77368617 -77368617 -77368617 -77368617 -77368617 -50022936 -77368617 -50022936 -77368617 -50022936 -77368617 -77368617 -77368617 -77368617 -77368617 -50022936 -50022936 -50022936 -50022936 -50022936 -77368617 -50022936 -50022936 -50022936 -50022936 -…

Example 2:

Input: 556 315917960 334904475 -718806290 -728394629 612982685 -768041262 -24949422 -315188508 -233954480 668504957 -616980761 73492151 -382105313 505558671 -693972184 -624855997 -986037402 -918377894 53885411 -38572178 -542541234 137845145 346670048 268668374 20998791 326895622 839664189 624207509 -72818156 471129247 -188443310 -519632535 597520543 594948067 392936134 732491956 -879282275 -364369493 -446309588 342979515 -815723794 960001819 881865792 -435582307 672015300 268603550 267779527 301460624 -990381053 679431453 742761051 23267803 -531394630 901796897 -3027739 342885533 612846570 121865909 179669844 693021630 -859121709 655045869 -70943297 -897913093 769865310 142149788 72010461 960576983 -8612238 -273518237 -882776715 133165241 -133107891 -570058278 -336402857 986364469 -354093028 -500…
Output: 315917960 315917960 315917960 -718806290 315917960 -718806290 -24949422 -315188508 -233954480 -233954480 -233954480 -233954480 -233954480 -233954480 -233954480 -315188508 -315188508 -382105313 -315188508 -315188508 -315188508 -315188508 -233954480 -233954480 -38572178 -38572178 -24949422 -24949422 -24949422 -24949422 -24949422 -38572178 -24949422 -24949422 20998791 20998791 20998791 -24949422 -24949422 -24949422 -24949422 -24949422 20998791 -24949422 20998791 20998791 53885411 53885411 53885411 53885411 73492151 53885411 53885411 53885411 53885411 53885411 73492151 73492151 121865909 121865909 121865909 121865909 121865909 73492151 121865909 121865909 121865909 121865909 121865909 73492151 73492151 73492151 73492151 72010461 72010461 72010461 72010461 53885411 72010461 53885411 72010461 53…

Example 3:

Input: 94 -111261235 143621205 -307661199 -371736970 -931557364 -445105223 -469176679 -139425862 -919082017 701687709 938132922 -160869253 -15170015 -305108344 -713018674 -171822292 -273492504 30769531 466818598 477009076 -555206679 -967878966 320335496 612050228 980236400 -780544012 322750316 353874504 22864389 -624805524 -316239005 987574940 842828474 72827891 247869051 400373083 366707072 -680734801 240640494 994718920 -603387891 504724564 95288038 -349513390 -733185266 717831271 -911843922 960435520 -333081308 -15515691 -555672147 -677023916 157861119 648481188 684141424 -747905058 -504391247 -653353042 893956507 928236416 -811472345 -645477451 -188554925 930655587 535225263 -120286418 704832279 -69100789 921176148 -830902544 322642807 -49152291 -396104178 829355572 200146825 -771774982 -1552…
Output: -111261235 -111261235 -111261235 -307661199 -307661199 -371736970 -371736970 -371736970 -371736970 -371736970 -307661199 -307661199 -160869253 -305108344 -305108344 -305108344 -273492504 -273492504 -171822292 -171822292 -171822292 -273492504 -171822292 -171822292 -160869253 -171822292 -160869253 -160869253 -139425862 -160869253 -160869253 -160869253 -139425862 -139425862 -111261235 -111261235 -15170015 -111261235 -15170015 -15170015 -15170015 -15170015 22864389 -15170015 -15170015 -15170015 -15170015 -15170015 -15170015 -15515691 -15515691 -111261235 -15515691 -15515691 -15170015 -15515691 -15515691 -111261235 -15515691 -15515691 -15515691 -111261235 -111261235 -111261235 -15515691 -111261235 -15515691 -69100789 -15515691 -69100789 -15515691 -49152291 -49152291 -49152291 -15515691 -4915229…

Constraints:

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

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