CT62557

Cartwright Counts the signals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Cartwright runs the mill at the lotus ponds of Tranquil Basin. Today the books show a list of signals, and the numbers must be worked out before sundown. 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: 2721 114793272 411883298 448230994 719857917 499131148 -17399157 -254932800 577840973 -273497961 -831449527 -385525851 -973796340 667516460 116633059 821140297 -17633434 351609692 904769486 -952785013 -279555222 224772872 153931058 -986342895 992478362 -234201876 716717584 -328816931 812758299 247119933 708084342 -453433098 577249912 75200944 387849947 -213769379 -745298557 107990346 25046283 802616537 612546010 822289380 39086691 -387322121 387053146 -457208222 -930541949 991261679 -717858149 781223210 -982008173 -986685164 -363047957 -39399086 568558602 -238029553 -344194456 -537661432 -429265602 -177370274 563378845 133086955 880315062 -809479360 -662565811 496699277 113930333 825594297 319928786 841266778 882133143 221854670 791911482 -803153197 212466896 -46729006 -383663689 529976486…
Output: 114793272 114793272 411883298 411883298 448230994 411883298 411883298 411883298 411883298 114793272 114793272 -17399157 114793272 114793272 116633059 114793272 116633059 116633059 116633059 114793272 116633059 116633059 116633059 116633059 116633059 116633059 116633059 116633059 153931058 153931058 153931058 153931058 153931058 153931058 153931058 116633059 116633059 114793272 116633059 116633059 153931058 116633059 116633059 116633059 116633059 114793272 116633059 114793272 116633059 114793272 114793272 107990346 107990346 107990346 107990346 75200944 75200944 39086691 39086691 39086691 75200944 75200944 75200944 39086691 75200944 75200944 107990346 107990346 113930333 113930333 114793272 114793272 114793272 114793272 114793272 113930333 114793272 113930333 114793272 113930333 113930333 1…

Example 2:

Input: 40 315682064 -143616247 356815323 -647819420 832535521 -699128359 118832729 233796398 -957173466 636719671 547765314 -642456242 866660034 -744692093 983387874 -680396523 717665958 -801282233 -738120977 -612758177 -299259758 -990964456 -218358765 162265013 -12531049 621027748 -255443666 -577231320 440796182 789411679 369812067 738045801 507773347 86608156 763651764 -584541369 -504210418 673792512 762250440 -786321151
Output: 315682064 -143616247 315682064 -143616247 315682064 -143616247 118832729 118832729 118832729 118832729 233796398 118832729 233796398 118832729 233796398 118832729 233796398 118832729 118832729 -143616247 -143616247 -299259758 -218358765 -218358765 -143616247 -143616247 -143616247 -218358765 -143616247 -143616247 -12531049 -12531049 118832729 86608156 118832729 86608156 86608156 86608156 118832729 86608156

Example 3:

Input: 3674 509164078 506256726 -99911409 -834795396 651639921 -472756260 477279679 -787867158 -962972939 -125020567 -179445584 -818565546 302414421 548091827 946559309 889220499 -75237688 766266784 -557640228 -703795529 948488628 951467638 -27568860 -358757173 344267700 -786808278 960399814 -955123515 972154845 394730080 958214279 60927047 -716609821 209290992 -887670881 -463720377 -865538096 899085014 -478654266 77160167 -546539098 866884807 -813599483 -586927889 -757429210 -407720132 647864446 259459718 -740756349 273000841 298767134 -758882957 395350120 62277047 408840183 361380807 146817010 -985901149 179077538 -470710362 574628360 -750532925 -925709978 -693792506 439901688 914826629 -390153153 961133931 -148459649 -114209929 382635166 215126535 708048006 -464527176 447394605 971373534 -8917…
Output: 509164078 506256726 506256726 -99911409 506256726 -99911409 477279679 -99911409 -99911409 -125020567 -125020567 -179445584 -125020567 -125020567 -99911409 -99911409 -75237688 -75237688 -75237688 -99911409 -75237688 -75237688 -27568860 -75237688 -27568860 -75237688 -27568860 -75237688 -27568860 -27568860 302414421 60927047 60927047 60927047 60927047 -27568860 -27568860 -27568860 -27568860 -27568860 -27568860 -27568860 -27568860 -75237688 -75237688 -99911409 -75237688 -75237688 -75237688 -75237688 -27568860 -75237688 -27568860 -27568860 60927047 60927047 62277047 60927047 62277047 60927047 62277047 60927047 60927047 -27568860 60927047 60927047 60927047 60927047 60927047 -27568860 60927047 60927047 62277047 60927047 62277047 62277047 62277047 62277047 62277047 60927047 60927047 -27568860 -275…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Cartwright Counts the signals - MEDIUM Coding Problem | CodeTikki