CT58813

The Middle So Far at Scriptoria

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Cartwright inherited the aviary at the ink district of Scriptoria along with its curious bookkeeping system for beacons. Time to make sense of it. 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: 3195 -595382636 -412253741 -137337246 207513462 175509695 470858420 677904261 -89346572 283769317 697663764 -941017021 3182769 135465179 -6495391 179991869 406622490 -743801448 751879313 816503958 774798320 108057998 -703475657 -111402651 351381615 -812674173 -92680982 -92224476 -539251523 -192176206 767959859 113253251 15756271 601870838 456932747 -332194297 -793913678 218052382 -706097251 311030480 -726015778 63578973 -184647720 -610376455 -892305173 -366049858 964066298 -577146665 433433639 258430623 792533746 453979118 -396432727 -442081228 -780144554 -736729305 200231048 129837539 -865422805 -13025452 317321229 -840847886 -30931240 76597177 -274628138 45189396 -242985851 -670111800 256725748 -34218499 -256229460 994370989 -803426644 318553102 669502289 -719609907 -744640099 -321164284…
Output: -595382636 -595382636 -412253741 -412253741 -137337246 -137337246 175509695 -89346572 175509695 175509695 175509695 3182769 135465179 3182769 135465179 135465179 135465179 135465179 175509695 175509695 175509695 135465179 135465179 135465179 135465179 108057998 108057998 3182769 3182769 3182769 108057998 15756271 108057998 108057998 108057998 15756271 108057998 15756271 108057998 15756271 63578973 15756271 15756271 3182769 3182769 3182769 3182769 3182769 15756271 15756271 63578973 15756271 15756271 3182769 3182769 3182769 15756271 3182769 3182769 3182769 3182769 -6495391 3182769 -6495391 3182769 -6495391 -6495391 -6495391 -6495391 -13025452 -6495391 -13025452 -6495391 -6495391 -6495391 -13025452 -13025452 -13025452 -6495391 -13025452 -6495391 -13025452 -13025452 -30931240 -30931240 -342184…

Example 2:

Input: 448 154771974 -327233265 113944031 -584042602 -181508357 373135124 -425821482 3104783 560031309 -687850388 922019245 -73687822 -595844258 871147599 430210665 724487879 812123130 798916997 -234559297 -593842720 231428906 285433559 767500343 -830374089 55884072 552594154 230160536 -696999818 828954322 967437949 -893974541 690259435 869651019 221380366 -656907240 -239004583 697848513 979231089 -32499988 250464991 755690941 310465416 -634950044 243585136 876798308 534790006 -964104688 -695022316 -362906197 637089064 123418910 -51252009 827193289 -235702280 994521944 83254434 -552428445 581212228 47905488 439354708 832547080 516673294 890703778 -580984888 292790563 -608828140 -858203666 622853045 384473749 -40387599 -719394732 -166216187 -825549037 173005184 259916809 -57270214 244619769 661403…
Output: 154771974 -327233265 113944031 -327233265 -181508357 -181508357 -181508357 -181508357 3104783 -181508357 3104783 -73687822 -73687822 -73687822 3104783 3104783 113944031 113944031 113944031 3104783 113944031 113944031 154771974 113944031 113944031 113944031 154771974 113944031 154771974 154771974 154771974 154771974 230160536 221380366 221380366 154771974 221380366 221380366 221380366 221380366 230160536 230160536 230160536 230160536 231428906 231428906 231428906 230160536 230160536 230160536 230160536 221380366 230160536 221380366 230160536 221380366 221380366 221380366 221380366 221380366 230160536 230160536 231428906 230160536 231428906 230160536 230160536 230160536 231428906 230160536 230160536 221380366 221380366 173005184 221380366 173005184 221380366 221380366 221380366 203015187 203…

Example 3:

Input: 2462 -990918265 -713435357 -292331319 771004484 -193948763 797217203 541620368 -80713537 48902171 838713659 -481138290 486718003 -127856219 -22594529 112313584 -598466141 -661554831 509210955 -163331096 505394881 244136904 160579250 433518969 -785215026 -3010843 -211062020 -891671082 -361913382 968515003 4108094 -688919780 -306192874 -66403497 469303631 288777291 -117089686 664996550 333897079 -558146197 -27714687 -877392449 -660025910 891107398 -747100014 673917752 -169385859 -991725716 -665258716 -278123326 837055890 -84037937 266466216 -682303438 -724269817 -850689018 -52150264 -278843418 487355694 -98906456 -525808552 877579323 -899913546 81879281 -329426749 -190492950 850128983 -866651462 -513028626 -461246347 -998751584 -623614030 759026803 -946456615 -557178812 669534887 -216765128 …
Output: -990918265 -990918265 -713435357 -713435357 -292331319 -292331319 -193948763 -193948763 -80713537 -80713537 -80713537 -80713537 -80713537 -80713537 -22594529 -80713537 -80713537 -80713537 -80713537 -80713537 -22594529 -22594529 48902171 -22594529 -3010843 -22594529 -22594529 -80713537 -22594529 -22594529 -22594529 -80713537 -66403497 -66403497 -22594529 -66403497 -22594529 -22594529 -22594529 -27714687 -27714687 -66403497 -27714687 -66403497 -27714687 -66403497 -66403497 -80713537 -80713537 -80713537 -80713537 -80713537 -80713537 -84037937 -84037937 -84037937 -84037937 -84037937 -84037937 -98906456 -84037937 -98906456 -84037937 -98906456 -98906456 -98906456 -98906456 -117089686 -117089686 -127856219 -127856219 -127856219 -127856219 -163331096 -127856219 -163331096 -127856219 -163331096 -12…

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