CT61974

Sara's Faded Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the monsoon port of Rainhaven. Sara 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: 700 183013171 804499511 93423272 -306701764 942397957 -973476315 651287466 -456357770 463937072 323979206 891893308 -339844274 693603128 -644117880 682780100 -601520105 95815466 -747048130 -577306445 221718997 405019702 -159893640 -614587992 -50745875 -856955617 16926532 -815999157 -214434317 612858439 -579921995 83166397 -334117777 805468168 68356592 -395973806 925302129 580506243 146420108 66726528 -404837636 953866673 713534557 -478363473 436451188 754476238 178792009 412157684 -841258318 -614139286 466125346 -236191725 -872992952 -37107698 155169108 247639935 842166992 -122012088 585170212 929700035 -26084169 111149079 -700293046 -225904229 -116647597 32983486 341685788 699892572 745216812 -127165420 -40339482 -581099310 641093308 -174669675 -305414674 807575951 922422943 726265193 -34…
Output: 183013171 183013171 183013171 93423272 183013171 93423272 183013171 93423272 183013171 183013171 323979206 183013171 323979206 183013171 323979206 183013171 183013171 95815466 95815466 95815466 183013171 95815466 95815466 93423272 93423272 16926532 16926532 -50745875 16926532 -50745875 16926532 -50745875 16926532 16926532 16926532 16926532 68356592 68356592 68356592 66726528 68356592 68356592 68356592 68356592 83166397 83166397 93423272 83166397 83166397 83166397 83166397 68356592 68356592 68356592 83166397 83166397 83166397 83166397 93423272 83166397 93423272 83166397 83166397 68356592 68356592 68356592 83166397 83166397 83166397 68356592 68356592 68356592 68356592 66726528 68356592 68356592 83166397 68356592 68356592 68356592 83166397 83166397 93423272 93423272 95815466 93423272 93423272…

Example 2:

Input: 3536 209247288 -493744260 71903052 761289689 -445548525 760528785 -643259078 -789933975 -158453021 221829291 -837354316 -977469028 398317551 -593628538 -403830647 240779799 970904701 428627681 -286202395 -938271880 -773138028 544820883 645343751 57412533 -325241571 931296780 -884551355 -399503337 908555756 974325086 66406778 -737400984 262260827 793091750 672080033 337809173 -989861594 615316830 -130147389 397655354 24174464 -959816420 850791885 145834696 355533359 115999232 -110821617 632113937 938804209 797009478 -474887744 564072749 456608106 851731448 443998555 982706144 241625094 829813402 -828285337 -35446656 -544665513 -400420812 320663088 -456389299 153130647 -59015274 -772849304 -138921348 659601495 580633746 586530003 -924275443 -940170770 789446741 -74204591 302260282 721586144 …
Output: 209247288 -493744260 71903052 71903052 71903052 71903052 71903052 -445548525 -158453021 -158453021 -158453021 -445548525 -158453021 -445548525 -403830647 -403830647 -158453021 -158453021 -158453021 -286202395 -286202395 -286202395 -158453021 -158453021 -158453021 -158453021 -158453021 -286202395 -158453021 -158453021 57412533 -158453021 57412533 57412533 66406778 66406778 66406778 66406778 66406778 66406778 66406778 57412533 66406778 66406778 71903052 71903052 71903052 71903052 115999232 115999232 115999232 115999232 145834696 145834696 209247288 209247288 221829291 221829291 221829291 209247288 209247288 145834696 209247288 145834696 153130647 145834696 145834696 115999232 145834696 145834696 153130647 145834696 145834696 145834696 145834696 145834696 153130647 153130647 209247288 1531306…

Example 3:

Input: 3394 -948020894 -57395055 -811276727 82113928 -891321811 -824533929 -77082184 -114709161 644425384 504369322 -832134919 229197516 -321921341 592599192 163980601 -291007341 991097519 850182624 -978058155 242191910 -323311360 -538726193 -354912301 -216589900 -34668710 -579582375 848671133 -974167406 277575948 279696817 283026851 385729076 20068562 219176121 730777854 924322710 -871699827 370992675 -196007041 -38722045 447051419 80756375 866286132 -954741477 -502802688 171872013 615299222 770689422 744809128 78240911 -850823930 -905319511 732777402 -488666514 -65242526 258579449 -755901183 -942220884 370058607 830940452 588491620 576564779 841809438 760162812 -276518647 -407748699 147355913 910708578 460382892 138884802 429691257 780774493 24518720 859023317 111922583 -720834370 -661087314 68…
Output: -948020894 -948020894 -811276727 -811276727 -811276727 -824533929 -811276727 -811276727 -114709161 -114709161 -114709161 -114709161 -114709161 -114709161 -77082184 -114709161 -77082184 -77082184 -77082184 -77082184 -77082184 -114709161 -114709161 -216589900 -114709161 -216589900 -114709161 -216589900 -114709161 -114709161 -77082184 -77082184 -57395055 -57395055 -34668710 -34668710 -34668710 -34668710 -34668710 -38722045 -34668710 -34668710 20068562 -34668710 -34668710 -34668710 20068562 20068562 80756375 78240911 78240911 20068562 78240911 20068562 20068562 20068562 20068562 -34668710 20068562 20068562 78240911 78240911 80756375 80756375 80756375 78240911 80756375 80756375 82113928 82113928 138884802 138884802 138884802 138884802 138884802 111922583 111922583 111922583 111922583 82113928 8…

Constraints:

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

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