CT61185

The signals at Thornveld

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the acacia flats of Thornveld, someone must assign crews to the morning shifts. This year the task falls to Tailor, armed only with the signals register. 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: 2250 -447938370 45506706 319807014 350920757 -854952908 -67101811 -134934853 -599953834 66887584 248834235 923952132 -89839384 -484448856 -268678769 -823008192 -590121977 544698210 -205840111 -955982957 149064875 245598125 -58716625 -36239425 585145083 582584027 123537581 -976130067 -82691903 531223910 -68378273 -769681874 -982985437 -284458213 -486751005 555805584 -11800390 468179149 656437056 262094738 255295188 -783669931 -651621551 -989351795 -233334752 129157848 343180158 212557687 -167615408 360546250 -358063678 -958841311 -181405860 1835313 14595829 728224290 970181445 135563213 -567115478 973095421 -885282183 973773854 -257042398 908219001 -456029009 701719829 -435726722 -919294465 817516694 -938853571 264312313 575761298 512972896 641238173 -51059961 -44306016 -255306331 -74988247…
Output: -447938370 -447938370 45506706 45506706 45506706 -67101811 -67101811 -134934853 -67101811 -67101811 45506706 -67101811 -67101811 -89839384 -89839384 -134934853 -89839384 -134934853 -134934853 -134934853 -89839384 -89839384 -67101811 -67101811 -58716625 -58716625 -58716625 -67101811 -58716625 -67101811 -67101811 -68378273 -68378273 -82691903 -68378273 -68378273 -67101811 -67101811 -58716625 -58716625 -58716625 -67101811 -67101811 -68378273 -67101811 -67101811 -58716625 -67101811 -58716625 -67101811 -67101811 -68378273 -67101811 -67101811 -58716625 -58716625 -36239425 -58716625 -36239425 -58716625 -36239425 -58716625 -36239425 -58716625 -36239425 -58716625 -58716625 -58716625 -58716625 -58716625 -36239425 -36239425 -11800390 -36239425 -36239425 -44306016 -44306016 -44306016 -44306016 -510599…

Example 2:

Input: 1608 487968161 -65581315 383902970 140771331 888532466 272476747 170902488 -952590920 407166046 -717728944 305798303 -837966716 178979694 -938303350 341699398 642250123 -695843279 614950399 -226694764 -646882688 650563630 942292070 -841663050 428941580 -522015975 -146058252 238332391 175739933 9212313 -110493416 -69970848 433247683 -942055773 -341269417 949382858 44996945 -934610921 337899760 -572189661 -170813179 49370845 -189715838 707034593 329770433 684586808 -441809693 102142858 8522061 137415889 608308381 968590452 233211441 -696318800 653044869 362944128 -337774029 680362382 390580590 279439482 -473414371 -154453258 488238481 -940383251 -867933847 859582344 558054591 712827610 -671044552 162809443 137013496 -894856888 -531161994 354537115 -201676352 556269496 -843555553 -446829508 -…
Output: 487968161 -65581315 383902970 140771331 383902970 272476747 272476747 170902488 272476747 170902488 272476747 170902488 178979694 170902488 178979694 178979694 178979694 178979694 178979694 170902488 178979694 178979694 178979694 178979694 178979694 170902488 178979694 175739933 175739933 170902488 170902488 170902488 170902488 140771331 170902488 140771331 140771331 140771331 140771331 44996945 49370845 44996945 49370845 49370845 140771331 49370845 102142858 49370845 102142858 102142858 137415889 137415889 137415889 137415889 140771331 137415889 140771331 140771331 170902488 140771331 140771331 140771331 140771331 137415889 140771331 140771331 170902488 140771331 162809443 140771331 140771331 137415889 140771331 137415889 140771331 137415889 137415889 137013496 137013496 137013496 1370134…

Example 3:

Input: 738 -132328007 971512067 152114733 -338638558 503868676 418712172 79855730 -277157422 434364621 64503603 354378595 47295414 -599143693 -16571589 -848084016 867858824 -680758313 -380592736 184318144 817624053 -832415357 522227254 -636507427 911440431 834165998 -770419937 475886455 923908697 631085066 -271785160 -708148097 249371236 344130589 720612849 481340710 -374894063 -794941073 -340062434 746562101 782689000 66393742 384233874 539750644 580672765 -635402498 291769111 -522423590 -785346629 -781654378 -985339561 -95683031 -178582900 679043947 859293831 -392349574 -798641691 635958102 193704484 -796420364 -822645556 888131937 806379735 822513540 -803549481 215051358 -995369191 748808182 -338148698 620174771 744372884 256041375 -50276483 393430036 668063976 -392831389 857051202 -270985535 …
Output: -132328007 -132328007 152114733 -132328007 152114733 152114733 152114733 79855730 152114733 79855730 152114733 79855730 79855730 64503603 64503603 64503603 64503603 47295414 64503603 64503603 64503603 64503603 64503603 64503603 79855730 64503603 79855730 79855730 152114733 79855730 79855730 79855730 152114733 152114733 184318144 152114733 152114733 79855730 152114733 152114733 152114733 152114733 184318144 184318144 184318144 184318144 184318144 152114733 152114733 79855730 79855730 66393742 79855730 79855730 79855730 66393742 79855730 79855730 79855730 66393742 79855730 79855730 152114733 79855730 152114733 79855730 152114733 79855730 152114733 152114733 184318144 152114733 184318144 184318144 184318144 184318144 184318144 184318144 193704484 193704484 215051358 193704484 193704484 184318…

Constraints:

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

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