CT63610

The beacons at Goldmeadow

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the trading post of Goldmeadow. Tanner spreads the beacons records across the table and picks up a sharp pencil. 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: 2733 866617606 213909237 358242691 -946357191 662457964 306074258 671920606 -990704566 893366227 -342208651 -258246083 294441885 197037193 -512767064 -840934356 783538884 607431798 440750489 -217593609 -63675721 233627490 670461197 981757148 456968183 181609718 -653701173 871373043 733805422 -264619296 -93897107 186389490 -342232945 822900205 499549690 196586798 903177598 756455428 -492183363 224063513 153732937 509235086 -827551015 206938924 746857223 216797352 -841476831 -108384779 -725505439 -338585078 -697267146 -5945224 -685784376 235318893 998596605 267047303 523971699 -742910207 -680963774 -633349432 -293253249 828923959 119794137 898177468 563360029 7775352 -690045947 -689131707 183492892 -79414514 -432268176 -514083956 587778396 -170437889 -495527562 -915646991 -46921246 427239231…
Output: 866617606 213909237 358242691 213909237 358242691 306074258 358242691 306074258 358242691 306074258 306074258 294441885 294441885 213909237 213909237 213909237 294441885 294441885 294441885 213909237 233627490 233627490 294441885 294441885 294441885 233627490 294441885 294441885 294441885 233627490 233627490 213909237 233627490 233627490 233627490 233627490 294441885 233627490 233627490 224063513 233627490 224063513 224063513 224063513 224063513 216797352 216797352 213909237 213909237 206938924 206938924 197037193 206938924 206938924 213909237 213909237 213909237 206938924 206938924 197037193 206938924 197037193 206938924 206938924 206938924 197037193 197037193 196586798 196586798 186389490 186389490 186389490 186389490 183492892 183492892 181609718 183492892 183492892 183492892 183492892 …

Example 2:

Input: 3916 -91867721 361891499 220336498 792267005 615726219 232868374 653995735 949518927 949444443 -92079439 -333074844 -210870874 -330877874 -671562978 114671007 837258793 -19990460 875670104 -728488053 -162307291 -707120512 -223747614 -661501594 304162598 764375330 -767635907 848362612 470050178 -523221358 634376893 -64074723 9888809 239484254 -554027410 -312910813 855135208 -510118212 761301951 -222396455 -393837318 -932851348 -57459736 875434722 -848664283 -480998994 855529281 855652446 220132539 -468583149 -443237476 960134390 -463955623 -920163366 315479557 -948445139 -531609072 759022321 -640309267 -982378600 348233222 -146690976 -607030631 879680501 -613042585 632612937 -26960405 199913109 583875107 -580425395 955054862 108550913 174638334 125383495 149621915 987746213 -949925363 98060…
Output: -91867721 -91867721 220336498 220336498 361891499 232868374 361891499 361891499 615726219 361891499 361891499 232868374 232868374 220336498 220336498 220336498 220336498 220336498 220336498 114671007 114671007 -19990460 -19990460 -19990460 114671007 -19990460 114671007 114671007 114671007 114671007 114671007 9888809 114671007 9888809 9888809 9888809 9888809 9888809 9888809 -19990460 -19990460 -57459736 -19990460 -57459736 -57459736 -57459736 -19990460 -19990460 -19990460 -57459736 -19990460 -57459736 -57459736 -57459736 -57459736 -64074723 -57459736 -64074723 -64074723 -64074723 -64074723 -91867721 -64074723 -91867721 -64074723 -64074723 -57459736 -57459736 -57459736 -57459736 -26960405 -26960405 -19990460 -19990460 9888809 -19990460 9888809 9888809 9888809 -19990460 9888809 -19990460 9888…

Example 3:

Input: 1097 755033163 -806109736 263201485 908396581 402161426 677008096 491170277 -975434708 -288998884 672063674 -284444882 -529051983 -726024616 114158513 332470253 24178497 -385688734 805498509 587031660 36215489 982252468 536036825 287487291 -278866085 -426395386 805730063 470456047 -914459571 988738964 538405893 589599140 617087162 -41512692 -290184112 438383148 484402964 371177907 764825666 -23243718 563857561 595888159 343142915 -306797588 755558409 545190963 -426793718 -627998111 564322201 73501655 -16021474 854698263 212764127 -62175137 195268018 -931030801 -183526571 -225346398 180215558 -643194416 653076086 -590679399 135694276 -186016310 651942170 -899368030 -496444616 218132719 -816621012 -516648701 -713016714 736825648 505630579 820947254 452185726 483727520 910467286 -994338662 -8…
Output: 755033163 -806109736 263201485 263201485 402161426 402161426 491170277 402161426 402161426 402161426 402161426 263201485 263201485 114158513 263201485 114158513 114158513 114158513 263201485 114158513 263201485 263201485 287487291 263201485 263201485 263201485 287487291 263201485 287487291 287487291 332470253 332470253 332470253 287487291 332470253 332470253 371177907 371177907 371177907 371177907 402161426 371177907 371177907 371177907 402161426 371177907 371177907 371177907 371177907 343142915 371177907 343142915 343142915 332470253 332470253 287487291 287487291 263201485 263201485 263201485 263201485 212764127 212764127 212764127 212764127 195268018 212764127 195268018 195268018 180215558 195268018 195268018 212764127 212764127 218132719 218132719 218132719 212764127 212764127 195268018…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.