CT58137

Zephyr's marks Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Zephyr inherited the ferry office at the shipyard of Keelwind along with its curious bookkeeping system for marks. 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: 2953 26732354 -882215810 270092903 543191355 80732786 -278558784 -209597195 352725579 -957465286 -774684504 529409468 472584300 -984121315 9837778 31794376 927489401 -316899226 -13283246 646710272 -6300875 -500396638 525586409 921648126 -310877123 823379582 226325682 -101071853 56619949 556939709 453779530 902135565 -610348148 555494381 921950456 545337866 47349927 917357016 871547317 265585874 -533350427 573098228 398979890 -142544394 971415829 514887531 -392418091 -794960026 899765046 -884709544 -630680456 839010011 -508140070 138819058 -10321213 -125340736 981177811 -511278995 -584595142 -980409509 -282582075 -658271341 -863049113 -241430059 470415292 -722951105 -356066475 652501151 999967979 -357270734 270634970 -112645601 2528101 -458097767 466319320 -491096145 903114009 730028811 430…
Output: 26732354 -882215810 26732354 26732354 80732786 26732354 26732354 26732354 26732354 -209597195 26732354 26732354 26732354 9837778 26732354 26732354 26732354 9837778 26732354 9837778 9837778 9837778 26732354 9837778 26732354 26732354 26732354 26732354 31794376 31794376 56619949 31794376 56619949 56619949 80732786 56619949 80732786 80732786 226325682 80732786 226325682 226325682 226325682 226325682 265585874 226325682 226325682 226325682 226325682 80732786 226325682 80732786 138819058 80732786 80732786 80732786 80732786 56619949 56619949 47349927 47349927 31794376 31794376 31794376 31794376 26732354 31794376 31794376 31794376 31794376 31794376 26732354 26732354 26732354 26732354 26732354 31794376 31794376 31794376 26732354 26732354 26732354 26732354 26732354 26732354 26732354 26732354 2673235…

Example 2:

Input: 3502 -370991173 -719912650 -227263142 -378542345 -826144337 868709279 -112412941 -839585601 289963820 9861779 446895814 -388382022 807803084 -19970321 330716324 -519710243 333360315 60620030 350420766 742091477 421576944 -282981912 826364409 -826601887 -51151643 909603098 -19954393 -747834746 -528506458 389893736 -390684728 392509499 954255123 -517299142 -50290437 470411624 753711401 603698818 306375701 -633683443 -83919342 -314018590 -181353728 151741593 -762489211 909984996 -507246530 194279063 536879551 -4246231 -868121669 20450289 875155014 822036414 -970031381 404598855 -961991377 -500361704 603088546 -835274249 844548586 -839613104 474542293 -580054549 339957700 -797906455 -981274734 655905447 827761741 239913067 -696177551 10125497 322622213 960026414 -632653839 -843420054 -10614952…
Output: -370991173 -719912650 -370991173 -378542345 -378542345 -378542345 -370991173 -378542345 -370991173 -370991173 -227263142 -370991173 -227263142 -227263142 -112412941 -227263142 -112412941 -112412941 -19970321 -19970321 9861779 -19970321 9861779 -19970321 -19970321 -19970321 -19954393 -19970321 -19970321 -19970321 -19970321 -19970321 -19954393 -19970321 -19970321 -19970321 -19954393 -19954393 9861779 -19954393 -19954393 -19970321 -19970321 -19970321 -19970321 -19970321 -19970321 -19970321 -19954393 -19954393 -19954393 -19954393 -4246231 -4246231 -4246231 -4246231 -4246231 -19954393 -4246231 -19954393 -4246231 -19954393 -4246231 -19954393 -4246231 -19954393 -19954393 -19954393 -4246231 -4246231 -4246231 -4246231 9861779 9861779 9861779 -4246231 -4246231 -4246231 9861779 -4246231 9861779 98617…

Example 3:

Input: 2383 -878048954 963850532 -351150308 42601625 519989342 299837569 250301390 714175199 458163134 994020246 858135840 -758577514 -853737408 394155334 138183849 -316430053 -653913431 -75147088 896049292 -227526030 517682646 890377501 531362789 608141573 79875437 345683769 970048229 -793620267 -129319305 643952481 -157731454 -199954133 232726404 -498557130 907480921 441161178 -951301912 837566496 -510403003 150930871 705190168 -469399134 -276155022 -520619361 -262971756 -811716750 579521787 551432196 -212582676 168148733 -103761945 874546275 -34934535 885520728 -877472850 -329571907 -298765514 -773094662 515478649 740174427 -806741315 -32484565 887008335 -506981208 -348330796 -366306843 -670902305 753650403 302302289 -762857920 -328578150 -836758352 -429424353 669873720 -339145553 547178394 91…
Output: -878048954 -878048954 -351150308 -351150308 42601625 42601625 250301390 250301390 299837569 299837569 458163134 299837569 299837569 299837569 299837569 250301390 250301390 138183849 250301390 138183849 250301390 250301390 299837569 299837569 299837569 299837569 345683769 299837569 299837569 299837569 299837569 250301390 250301390 232726404 250301390 250301390 250301390 250301390 250301390 232726404 250301390 232726404 232726404 150930871 150930871 138183849 150930871 150930871 150930871 150930871 150930871 150930871 150930871 150930871 150930871 138183849 138183849 79875437 138183849 138183849 138183849 79875437 138183849 79875437 79875437 42601625 42601625 42601625 79875437 42601625 42601625 -32484565 -32484565 -32484565 -32484565 -32484565 42601625 -32484565 42601625 -32484565 42601625 -…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Zephyr's marks Middle So Far - MEDIUM Coding Problem | CodeTikki