CT58446

Shepherd and the Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the old quarter of Brasshaven as Shepherd unrolls the day's manifest of marks. The tally will decide the next shipment. 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: 1305 393730078 424181487 -62939335 216810569 847007182 -387673044 732677495 261123018 538014622 259172969 -45314760 563584262 -610888872 991188239 527863987 694459654 -139965976 -943801300 -169101804 236365352 -388327504 -452402335 683561019 -736182505 -9529678 -462181494 833385793 -623269884 108122749 -801835332 375141406 512838712 -712610245 630633969 516506174 -961171292 -644810215 -425721668 -102154354 -193425745 727674008 -847507238 84720709 -139978489 -11717294 955364110 -730015702 -320791009 -818238272 276126513 365714017 -973356520 552202048 -466530234 76171790 -133839086 -884493840 265745872 -221651992 -667488185 77699150 -264460434 884876728 -808802052 -613084219 -632763282 133826210 -170443564 647910696 -431207093 922192173 -337781862 357273832 625308493 960498241 -701686677 322…
Output: 393730078 393730078 393730078 216810569 393730078 216810569 393730078 261123018 393730078 261123018 261123018 261123018 261123018 261123018 393730078 393730078 393730078 261123018 261123018 259172969 259172969 236365352 259172969 236365352 236365352 216810569 236365352 216810569 216810569 108122749 216810569 216810569 216810569 216810569 236365352 216810569 216810569 108122749 108122749 -9529678 108122749 -9529678 84720709 -9529678 -9529678 -9529678 -9529678 -11717294 -11717294 -11717294 -9529678 -11717294 -9529678 -11717294 -9529678 -11717294 -11717294 -11717294 -11717294 -45314760 -11717294 -45314760 -11717294 -45314760 -45314760 -62939335 -45314760 -62939335 -45314760 -62939335 -45314760 -62939335 -45314760 -45314760 -11717294 -45314760 -11717294 -11717294 -9529678 -9529678 -9529678 -95…

Example 2:

Input: 509 -934432598 -657426932 110393676 558350123 192259911 -730184846 972280689 573125916 -166134863 -777697156 832630340 247533074 359785345 -304439952 192728923 -454295831 453804003 -201559689 305177577 -671161012 564526202 368283141 -988739293 -974052788 907602365 328734342 313671979 832420903 768259546 585706225 847647125 -967376888 -365973050 594877837 922736809 -531322330 -803729559 -689379716 -450643335 -234767364 872827016 -635155537 713335070 177541246 499634617 -277604107 41127097 -783005484 897306719 -224665939 239023185 -644848269 832055132 -696745221 -630752683 299451 433850441 463550517 -731234885 395470641 330115206 229196076 86136314 -291914375 -244134956 881804139 418521879 -462782715 -724072249 903388107 659858803 387565057 980971987 -889700849 -745592068 -880224412 56487911…
Output: -934432598 -934432598 -657426932 -657426932 110393676 -657426932 110393676 110393676 110393676 -166134863 110393676 110393676 192259911 110393676 192259911 110393676 192259911 110393676 192259911 110393676 192259911 192259911 192259911 110393676 192259911 192259911 192728923 192728923 247533074 247533074 305177577 247533074 247533074 247533074 305177577 247533074 247533074 192728923 192728923 192259911 192728923 192259911 192728923 192259911 192728923 192259911 192259911 177541246 192259911 177541246 192259911 177541246 192259911 177541246 177541246 110393676 177541246 177541246 177541246 177541246 192259911 192259911 192259911 177541246 177541246 177541246 192259911 177541246 177541246 177541246 192259911 192259911 192728923 192259911 192259911 177541246 192259911 177541246 177541246 1775…

Example 3:

Input: 3145 701400880 247633535 -824566901 714062849 -312208661 561667359 -705159807 897827938 -705548041 -721950140 -694522721 790982854 23047295 458761917 482715985 -918723801 804394868 808029244 -905585594 98501093 -641129953 -3372980 -982436764 -318607260 -582392304 40037966 982640418 232096529 -771659096 -777083600 -435903348 -849475234 891805879 64211893 621364300 558186772 -870991109 -839341367 655826548 498664463 562439171 511955764 897146187 -800483166 417082302 -718995637 -47049396 -894559667 502432614 -16888338 977242292 243731221 -310467300 -305553477 -904573046 296289339 -274348268 358617697 -878353542 -460478244 -306568901 885123922 299956934 147572656 703549944 -1758996 -972643660 181485728 -615349709 -12676915 -263988 591574287 -20646612 157510839 -607177684 311962656 234923939 -2…
Output: 701400880 247633535 247633535 247633535 247633535 247633535 247633535 247633535 247633535 -312208661 -312208661 -312208661 23047295 23047295 247633535 23047295 247633535 247633535 247633535 98501093 98501093 23047295 23047295 -3372980 -3372980 -3372980 23047295 23047295 23047295 -3372980 -3372980 -312208661 -3372980 -3372980 23047295 23047295 23047295 -3372980 23047295 23047295 40037966 40037966 64211893 40037966 64211893 40037966 40037966 23047295 40037966 23047295 40037966 40037966 40037966 23047295 23047295 23047295 23047295 23047295 23047295 -3372980 -3372980 -3372980 23047295 23047295 40037966 23047295 23047295 23047295 23047295 -1758996 -263988 -263988 -263988 -263988 -263988 -263988 23047295 -263988 23047295 -263988 23047295 -263988 23047295 -263988 -263988 -263988 -263988 -1758996 …

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Shepherd and the Middle So Far - MEDIUM Coding Problem | CodeTikki