CT61734

Ysolde's Hidden marks

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the tundra station of Whitesnow, Ysolde the cartographer keeps careful count of the marks. Prepare the expedition manifest, every figure matters. 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: 482 475711192 148668043 527870156 556206785 -96339198 667436188 794738703 -234973587 569175850 963710556 -100878574 -351361951 895599380 60583475 -69287679 -663644119 -422168103 274408158 880161619 325360468 -112218575 548874405 -510100671 716174584 -678776061 573041444 551153177 62529074 -26688559 -704866120 579318161 750836650 -412455931 -85610913 -910695531 709426094 -708260976 -280063020 -296548715 415515494 -150379332 687621842 80230359 913014158 -473059164 9610643 -802502552 357492134 -819598270 713831803 -338486463 756164153 -887497289 -847124393 -98974369 -274717734 628480721 437375427 -867641078 -856768539 920926987 -336543961 -496149812 580761594 -775196819 43789459 311175305 295961462 217253291 -104457104 -484176592 -582455118 -386422154 -64010014 544522761 123100747 -353463489 …
Output: 475711192 148668043 475711192 475711192 475711192 475711192 527870156 475711192 527870156 527870156 527870156 475711192 527870156 475711192 475711192 148668043 148668043 148668043 274408158 274408158 274408158 274408158 274408158 274408158 274408158 274408158 325360468 274408158 274408158 148668043 274408158 274408158 274408158 148668043 148668043 148668043 148668043 62529074 62529074 62529074 62529074 62529074 80230359 80230359 80230359 62529074 62529074 62529074 62529074 62529074 62529074 62529074 62529074 60583475 60583475 9610643 60583475 60583475 60583475 9610643 60583475 9610643 9610643 9610643 9610643 9610643 43789459 43789459 60583475 43789459 43789459 9610643 9610643 -26688559 9610643 9610643 9610643 -26688559 -26688559 -64010014 -64010014 -64010014 -26688559 -26688559 -26688559 -…

Example 2:

Input: 1774 989514576 322745970 -561178819 -70949156 -591610859 786639610 840886302 -916936927 -329523445 -693831891 -245397101 436053028 189361030 -935790221 -589849805 -549122205 -947340359 729737949 -965895630 618708160 -842499358 640131242 -410231043 35256522 -821140301 337662463 -206706171 -894252466 527798918 -357256988 -986623885 -46975764 14226597 -821227312 -562150061 -654094729 72667057 60717419 272308407 -29335387 -107813228 -414824435 605502383 -501330327 921887549 671888465 713331433 -977008700 -682427450 -254731147 -919087879 783148499 601237971 -501871214 -292168159 176510013 -255379642 234009006 32744204 834968339 -728680534 -93997683 985470309 7943610 -307446090 705032332 -534735548 -583608434 132860281 622693118 -22143339 280596374 858118933 99807197 -758651251 2579886 -88794507…
Output: 989514576 322745970 322745970 -70949156 -70949156 -70949156 322745970 -70949156 -70949156 -329523445 -245397101 -245397101 -70949156 -245397101 -245397101 -329523445 -329523445 -329523445 -329523445 -329523445 -329523445 -329523445 -329523445 -329523445 -329523445 -329523445 -245397101 -329523445 -245397101 -329523445 -329523445 -329523445 -245397101 -329523445 -329523445 -357256988 -329523445 -329523445 -245397101 -245397101 -206706171 -245397101 -206706171 -245397101 -206706171 -206706171 -107813228 -206706171 -206706171 -245397101 -245397101 -245397101 -206706171 -245397101 -245397101 -245397101 -245397101 -245397101 -206706171 -206706171 -206706171 -206706171 -107813228 -107813228 -107813228 -107813228 -107813228 -206706171 -107813228 -107813228 -93997683 -93997683 -70949156 -70949156 …

Example 3:

Input: 3955 -461585099 -326222790 19600322 -221632281 -490715738 -554142936 -82365481 529869626 301040110 86429536 575313296 -462544386 525788547 816306583 -524701553 192936139 -15158365 -509540073 -949069493 182106727 288497160 917968525 800319243 -715956683 -619893996 -948557371 503909070 841155333 667714720 96685386 -701902076 -947220649 441609447 -245305924 -145095952 510201934 -565325824 610662522 193915702 -407900390 328792755 626940759 894645391 796461399 -930034373 62354990 347781643 -780555548 989215194 80507678 525018721 20494835 469236982 -817471364 -33264134 -721834860 -602496842 -582543861 -889646742 -319346586 -122879808 -546722364 672490120 -114195259 -393736751 178830236 363872396 -921523429 -912077941 -877078987 907698630 -167822836 -407695365 516945364 380314182 725960564 400479…
Output: -461585099 -461585099 -326222790 -326222790 -326222790 -461585099 -326222790 -326222790 -221632281 -221632281 -82365481 -221632281 -82365481 -82365481 -82365481 -82365481 -15158365 -82365481 -82365481 -82365481 -15158365 -15158365 19600322 -15158365 -15158365 -82365481 -15158365 -15158365 19600322 19600322 19600322 -15158365 19600322 -15158365 -15158365 -15158365 -15158365 -15158365 19600322 -15158365 19600322 19600322 86429536 86429536 86429536 62354990 86429536 62354990 86429536 80507678 86429536 80507678 86429536 80507678 80507678 62354990 62354990 20494835 20494835 19600322 19600322 -15158365 19600322 -15158365 -15158365 -15158365 19600322 -15158365 -15158365 -33264134 -15158365 -33264134 -33264134 -33264134 -15158365 -15158365 19600322 -15158365 19600322 19600322 20494835 20494835 204…

Constraints:

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

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