CT58432

The Northern Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the floating docks of Skyharbor with crates of beacons, and Rosa the inventory keeper must account for every last one. 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: 1427 -912817980 -604260484 -276371473 -918045216 -781479094 -545478343 -147156169 775415811 860944191 -768682404 338799255 995110204 655855231 -244953659 424515421 -698762525 -106664142 -757286251 709038475 -76467899 -208813883 -963736261 -705354221 538448155 397334777 320811683 -129857200 636442116 276897262 190384629 -838195082 166218077 242737885 360628672 -906937114 -754894174 636047450 -698377344 -783574583 163342867 -513678012 673682368 -288955716 -91285452 -823569760 -403065424 -838755663 559739628 60276359 673859755 206421770 946366912 -162133985 -997231628 -923805018 317917870 -974712288 -649154558 734176715 420060859 -227583161 -123535371 895565263 182236916 -964307366 -443897893 -889317970 -716819287 -160829749 -125497792 -727830198 -554283043 953584415 283186780 -83842172 -1427…
Output: -912817980 -912817980 -604260484 -912817980 -781479094 -781479094 -604260484 -604260484 -545478343 -604260484 -545478343 -545478343 -276371473 -276371473 -244953659 -276371473 -244953659 -276371473 -244953659 -244953659 -208813883 -244953659 -244953659 -244953659 -208813883 -208813883 -147156169 -147156169 -129857200 -129857200 -129857200 -129857200 -106664142 -106664142 -106664142 -129857200 -106664142 -129857200 -129857200 -129857200 -129857200 -129857200 -129857200 -129857200 -129857200 -147156169 -147156169 -147156169 -129857200 -129857200 -106664142 -106664142 -106664142 -129857200 -129857200 -129857200 -129857200 -147156169 -129857200 -129857200 -129857200 -129857200 -123535371 -123535371 -123535371 -129857200 -129857200 -147156169 -147156169 -147156169 -147156169 -160829749 -1471561…

Example 2:

Input: 3470 -412627997 115506666 579365722 919690004 -169597473 883263171 322839395 734676582 307575723 598229314 -92384201 265587519 477878800 938039425 16735753 -428516958 611942584 -934748220 -716046913 -727039704 261957947 640696783 67209783 672183536 771595796 514128124 -806623719 -982003136 450973606 208839599 -874357931 661571479 667161704 -310009688 35614589 914638096 75110390 -665938781 -324698680 -580926142 543787639 -396859930 170730220 -552946257 -35208428 -376862366 113249586 606493925 -526775606 -811186148 -832830325 -448341599 -878174644 -608913250 955444991 318743035 226160577 -937229901 -33258323 -593950431 991751430 692403568 284783436 -212297435 729815838 -994381176 172006164 -471439015 43637901 726840353 -940100022 -792620475 473580723 715034183 -252885764 -487059712 974439460…
Output: -412627997 -412627997 115506666 115506666 115506666 115506666 322839395 322839395 322839395 322839395 322839395 307575723 322839395 322839395 322839395 307575723 322839395 307575723 307575723 265587519 265587519 265587519 265587519 265587519 307575723 307575723 307575723 265587519 307575723 265587519 265587519 265587519 307575723 265587519 265587519 265587519 265587519 261957947 261957947 208839599 261957947 208839599 208839599 170730220 170730220 115506666 115506666 115506666 115506666 113249586 113249586 75110390 75110390 67209783 75110390 75110390 113249586 75110390 75110390 67209783 75110390 75110390 113249586 75110390 113249586 75110390 113249586 75110390 75110390 75110390 75110390 67209783 75110390 75110390 75110390 67209783 75110390 75110390 113249586 113249586 115506666 113249586 1…

Example 3:

Input: 419 394045191 149870730 -838999725 776196569 498519234 -190568168 297201031 258212245 70241537 -465766373 -458316272 -924851904 -885364030 -893442271 950361475 -758596239 -196185642 401477821 -79051536 -782327195 279158657 -412035849 880129201 -219851113 -723120806 -190014174 -659532814 -532022827 -740330584 87201454 356993540 583082298 -410039983 423816004 469473302 -628800214 -549598225 -772881146 858092155 902858064 934698606 -782480844 537906270 -215506793 -232373296 -791125403 933760726 -658295946 409950728 37811846 -421244090 -424038091 -40767005 217739047 127919165 543905634 -1161150 798685759 -730876164 371181787 467423880 37427807 -347950230 -864307003 276569548 79571872 -78510836 757185948 -955296476 935193810 524778383 760694292 -935897605 983635869 810925451 39248247 -416615968…
Output: 394045191 149870730 149870730 149870730 394045191 149870730 297201031 258212245 258212245 149870730 149870730 70241537 70241537 -190568168 70241537 -190568168 -190568168 -190568168 -79051536 -190568168 -79051536 -190568168 -79051536 -190568168 -190568168 -190568168 -190568168 -196185642 -196185642 -196185642 -190568168 -190568168 -190568168 -190568168 -190014174 -190568168 -190568168 -196185642 -190568168 -190568168 -190014174 -190568168 -190014174 -190568168 -190568168 -196185642 -190568168 -196185642 -190568168 -190568168 -190568168 -196185642 -190568168 -190568168 -190014174 -190014174 -79051536 -79051536 -79051536 -79051536 -40767005 -40767005 -40767005 -79051536 -40767005 -40767005 -40767005 -40767005 -40767005 -40767005 -1161150 -1161150 -1161150 -1161150 37427807 37427807 37427807 3…

Constraints:

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

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