CT57308

The Middle So Far Beneath Sunspire

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Xanthe found an old ledger of signals in the granary attic at the temple city of Sunspire. The margin notes pose a precise question. 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: 1264 981904420 -213642357 418911090 72570852 745435069 -47448947 895812384 -820927278 -305174620 930645996 621319287 -674990577 -272076052 871444379 -303849115 -444509768 478318402 162832478 -106693259 -153902230 -323989868 49991779 -653728030 362966047 70434528 -143304093 636674507 215076951 951104892 379593850 -964771946 418838535 258940091 932048680 -523062870 -1523376 490378575 799575033 -511939271 997410835 683587935 927017763 744450323 392606477 -81691065 892239622 -221342577 -681000780 789222428 -69864816 201155504 -387483922 -607975502 833306387 -492736333 725038730 155247179 -313249950 279500204 -248717505 -119644454 -831327017 891997885 -861402654 -809089327 847420740 529753959 681836132 939447363 -548166713 -398956485 783125948 -191359823 51195555 -254483150 469209472 414240744 …
Output: 981904420 -213642357 418911090 72570852 418911090 72570852 418911090 72570852 72570852 72570852 418911090 72570852 72570852 72570852 72570852 -47448947 72570852 72570852 72570852 -47448947 -47448947 -47448947 -47448947 -47448947 49991779 -47448947 49991779 49991779 70434528 70434528 70434528 70434528 72570852 72570852 72570852 70434528 72570852 72570852 72570852 72570852 162832478 162832478 215076951 215076951 215076951 215076951 215076951 162832478 215076951 162832478 201155504 162832478 162832478 162832478 162832478 162832478 162832478 155247179 162832478 155247179 155247179 72570852 155247179 72570852 72570852 72570852 155247179 155247179 162832478 155247179 155247179 155247179 155247179 72570852 72570852 72570852 155247179 155247179 162832478 162832478 162832478 155247179 162832478 155…

Example 2:

Input: 3280 278853940 -462891813 -754308187 171994004 -989132668 -496726233 86532544 861158487 -508653505 -125445293 -277557268 33255579 57232373 -278229151 469782056 -721225079 662915980 695359672 253990693 -481153564 623491204 -402332257 509067936 184926610 310061364 -56455637 791127533 794220876 849563071 46541479 151186650 -189415755 -945327555 -378791224 -34949204 -123197457 345630426 826062928 281978248 -728306884 561745115 273394431 525577048 -294769614 -99446507 -854314161 721038289 739418489 787366368 180848017 -956005617 -289234892 -807176149 841029326 28317241 466218987 602587084 519452369 -210089959 884182503 419261703 -605133578 77023076 924010617 -236800310 463750251 739845764 412721910 -137578035 -240411506 507973764 -426910873 758957069 141984664 -572366659 730912633 -149895234 66…
Output: 278853940 -462891813 -462891813 -462891813 -462891813 -496726233 -462891813 -462891813 -462891813 -462891813 -277557268 -277557268 -125445293 -277557268 -125445293 -277557268 -125445293 -125445293 33255579 -125445293 33255579 -125445293 33255579 33255579 57232373 33255579 57232373 57232373 86532544 57232373 86532544 57232373 57232373 46541479 46541479 33255579 46541479 46541479 57232373 46541479 57232373 57232373 86532544 57232373 57232373 46541479 57232373 57232373 86532544 86532544 86532544 57232373 57232373 57232373 57232373 57232373 86532544 86532544 86532544 86532544 151186650 86532544 86532544 86532544 86532544 86532544 151186650 151186650 151186650 86532544 151186650 86532544 151186650 141984664 141984664 141984664 141984664 141984664 141984664 141984664 141984664 86532544 86532544 …

Example 3:

Input: 3412 759444201 -120887929 -601428002 -113016152 337743254 427654352 -485350693 952994043 -682828980 221780108 521663342 60246751 797567717 977719258 87609519 831627243 650191173 229362742 -189741301 -367633979 108080024 992483305 415216009 -467023646 -303445362 121513223 846741780 -507366105 -966847099 717793568 557277526 509371172 64293809 -276883993 -96794005 461746413 774455165 -730178446 969854990 524486931 19029235 -250121011 443790732 -715050193 -488319012 886735995 393150177 563121087 -37539270 -517304801 -532207761 -178456590 844468790 87096033 -461013009 481128867 -361320554 670815820 417577361 -842820331 -547967136 920324950 -149945292 -979173401 -659934624 -245812705 81589314 750414683 -797424255 -760329156 983742295 81344238 -470175768 236009261 -218700678 630282727 -765967819 …
Output: 759444201 -120887929 -120887929 -120887929 -113016152 -113016152 -113016152 -113016152 -113016152 -113016152 221780108 60246751 221780108 221780108 221780108 221780108 337743254 229362742 229362742 221780108 221780108 221780108 229362742 221780108 221780108 121513223 221780108 121513223 121513223 121513223 221780108 221780108 221780108 121513223 121513223 121513223 221780108 121513223 221780108 221780108 221780108 121513223 221780108 121513223 121513223 121513223 221780108 221780108 221780108 121513223 121513223 108080024 121513223 108080024 108080024 108080024 108080024 108080024 121513223 108080024 108080024 108080024 108080024 87609519 87609519 87096033 87096033 87096033 87096033 81589314 87096033 81589314 81589314 81589314 81589314 81589314 81589314 81589314 81589314 81589314 87096033 …

Constraints:

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

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