CT59066

The Middle So Far at Scarlet Plain

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the poppy fields of Scarlet Plain opens only for a perfect tally of ledgers. Wren means to find out. 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: 1391 -355568674 -541658175 -375318336 484088123 -695486957 -643982582 -316566550 367142036 694198019 88727269 -253354103 664256776 -110579495 773362016 -528210111 -425309796 -348294954 184574921 183435972 313385161 -372354852 -697399372 574104912 -525472464 -193037223 -534511690 -100872169 872341169 -998712098 241264256 132883231 781538365 523953848 -417069195 -794113948 -484371900 -868846948 -771498429 -450376450 -585307900 -476973838 -567101004 497529416 967413082 -87102742 -79399378 631474575 461907782 628282423 -592852143 -620729606 619095146 -817850418 -807004026 -541936779 -661384997 -815085494 209422845 -140166420 130445498 616065800 291846741 838337269 744400080 -318015960 166350253 -271267981 -19551363 -903017392 405114838 -878902018 71427294 373451483 309015916 660142280 95006323…
Output: -355568674 -541658175 -375318336 -375318336 -375318336 -541658175 -375318336 -375318336 -355568674 -355568674 -316566550 -316566550 -253354103 -253354103 -253354103 -316566550 -316566550 -316566550 -253354103 -253354103 -253354103 -316566550 -253354103 -316566550 -253354103 -316566550 -253354103 -253354103 -253354103 -253354103 -193037223 -193037223 -110579495 -193037223 -193037223 -253354103 -253354103 -316566550 -316566550 -348294954 -348294954 -355568674 -348294954 -348294954 -316566550 -316566550 -253354103 -253354103 -193037223 -253354103 -253354103 -253354103 -253354103 -316566550 -316566550 -348294954 -348294954 -348294954 -316566550 -316566550 -253354103 -253354103 -193037223 -193037223 -193037223 -193037223 -193037223 -193037223 -193037223 -193037223 -193037223 -193037223 -1401664…

Example 2:

Input: 1896 770906234 -763543844 172796566 959228874 -72057053 756600933 706020822 435292735 -916855453 -732593465 -509912384 769445571 -502586193 289725277 -726225858 -361132394 -34441231 220878484 534639771 570048378 -537526327 -517802074 180890095 -562426231 876373646 225857285 342493536 108693525 -487961224 355102614 -285326724 -382675821 -112374285 -397663782 587286470 773329685 134288524 -163433915 1202292 -677330027 219814294 -581587497 -745565742 -20290272 -293229235 336175977 469996143 -110065252 -877994331 -594027541 -163387925 -354699470 721922528 -389567195 732017037 -367804381 858078938 -76557327 107726631 500841089 -940499303 -768904737 368606685 -612541090 509555093 649562154 288573183 -771572991 783818266 -795682751 539201410 537488541 -436296345 562816309 708717139 518335472 5660…
Output: 770906234 -763543844 172796566 172796566 172796566 172796566 706020822 435292735 435292735 172796566 172796566 172796566 172796566 172796566 172796566 -72057053 -34441231 -34441231 172796566 172796566 172796566 -34441231 172796566 -34441231 172796566 172796566 180890095 172796566 172796566 172796566 172796566 108693525 108693525 -34441231 108693525 108693525 134288524 108693525 108693525 1202292 108693525 1202292 1202292 -20290272 -20290272 -20290272 1202292 -20290272 -20290272 -34441231 -34441231 -72057053 -34441231 -72057053 -34441231 -72057053 -34441231 -72057053 -34441231 -34441231 -34441231 -72057053 -34441231 -72057053 -34441231 -34441231 -20290272 -34441231 -20290272 -34441231 -20290272 -20290272 -20290272 -20290272 1202292 1202292 107726631 107726631 107726631 1202292 107726631 107…

Example 3:

Input: 2372 -891081463 271933902 -589629886 -673346649 921544662 -511242409 -486160695 -102011555 377660418 -738699151 -407309184 37863294 -265474769 466571937 -931072891 -877987003 821168071 952009106 -573721260 189645744 672302234 733937444 418878495 -448866110 -537048928 801637957 245724105 -422396276 -278102107 -955883291 650520320 -195970889 -133242957 -644552753 593563358 775176991 -300140849 773321869 -625050403 -510779823 -888043390 -898282115 -73759094 172453110 -162209836 -160809435 532345423 -44808222 917559818 501240350 -413131563 163134457 239474789 -468649423 -198712399 -258310592 765090309 -491320365 -566625653 816622344 -791476228 -548122411 922996376 855876885 -914783626 -586655583 -320721443 122915949 -835371085 869270011 -534685002 56651706 773376503 -150836990 177711080 -88865…
Output: -891081463 -891081463 -589629886 -673346649 -589629886 -589629886 -511242409 -511242409 -486160695 -511242409 -486160695 -486160695 -407309184 -407309184 -407309184 -486160695 -407309184 -407309184 -407309184 -407309184 -265474769 -265474769 -102011555 -265474769 -265474769 -265474769 -102011555 -265474769 -265474769 -278102107 -265474769 -265474769 -195970889 -265474769 -195970889 -195970889 -195970889 -195970889 -195970889 -265474769 -265474769 -278102107 -265474769 -265474769 -195970889 -195970889 -162209836 -162209836 -160809435 -160809435 -160809435 -160809435 -133242957 -160809435 -160809435 -162209836 -160809435 -162209836 -162209836 -162209836 -162209836 -195970889 -162209836 -162209836 -162209836 -195970889 -195970889 -195970889 -195970889 -195970889 -195970889 -195970889 -1622098…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Middle So Far at Scarlet Plain - MEDIUM Coding Problem | CodeTikki