CT57967

The Middle So Far at Firewatch

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the caldera rim of Firewatch, someone must schedule the next expedition. This year the task falls to Morgana, armed only with the marks 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: 2455 -65088313 -182349285 -974443821 934835279 20708337 438756180 826684806 -2781951 664182869 930940376 154855012 305069635 -949088197 447405650 603780098 639616500 863087068 -140985639 -955891607 -66875370 -382647144 -765240504 -481919944 -908085354 141249888 566704527 -105191644 -796217631 568872065 -342079677 -255125205 649160086 823665731 460939997 464126288 -912630640 844253885 -3052289 184645011 461413912 147095098 -459985772 -550550105 -449559814 -172372657 -77430135 -499336823 180041519 -510094228 -49122155 -199916599 -440131020 -551232944 -839865619 363145560 -104579123 -851950831 89723249 816305139 120609178 892589707 532156198 413381506 124992119 142835115 43862397 168331797 -625581198 926612190 747144210 -912782216 -643900832 333363560 -667718197 120387847 254130050 97523277 5…
Output: -65088313 -182349285 -182349285 -182349285 -65088313 -65088313 20708337 -2781951 20708337 20708337 154855012 154855012 154855012 154855012 305069635 305069635 438756180 305069635 305069635 154855012 154855012 20708337 20708337 -2781951 20708337 20708337 20708337 -2781951 20708337 -2781951 -2781951 -2781951 20708337 20708337 141249888 20708337 141249888 20708337 141249888 141249888 147095098 141249888 141249888 20708337 20708337 -2781951 -2781951 -2781951 -2781951 -3052289 -3052289 -49122155 -49122155 -65088313 -49122155 -65088313 -65088313 -65088313 -49122155 -49122155 -3052289 -3052289 -2781951 -2781951 20708337 20708337 43862397 20708337 43862397 43862397 43862397 20708337 43862397 20708337 43862397 43862397 89723249 89723249 89723249 89723249 97523277 97523277 120387847 97523277 9752327…

Example 2:

Input: 2598 -222899474 -478346573 -833784146 87869579 28314874 -514356280 521549869 -230723105 -858562582 -73928612 -745313465 -220707134 -686770083 639058284 587004070 139725487 -760693515 647841873 502227767 616624572 -297665759 934168865 448105824 215215598 -728406490 -548769160 -464245596 133842692 352383411 708364112 -396301991 350403696 -604497573 -229384273 418390048 20477966 710457883 -236169180 227154783 123929252 517836984 -875645494 910879972 -126281483 -80370892 28433900 -321581328 29421797 428368510 712246875 -8332186 -369191859 -320335214 -407173433 676243347 -995801005 217695483 -930509250 363604664 -790300087 966574304 -588623895 809965824 -287432831 858131578 -592158737 185569532 -220693888 -405123041 375533932 457801403 880086912 -636274343 -961493218 354356693 617472551 -421344…
Output: -222899474 -478346573 -478346573 -478346573 -222899474 -478346573 -222899474 -230723105 -230723105 -230723105 -230723105 -230723105 -230723105 -230723105 -222899474 -222899474 -222899474 -222899474 -220707134 -220707134 -220707134 -220707134 -73928612 -73928612 -73928612 -220707134 -220707134 -220707134 -73928612 -73928612 -73928612 -73928612 -73928612 -220707134 -73928612 -73928612 20477966 -73928612 20477966 20477966 28314874 20477966 28314874 20477966 20477966 20477966 20477966 20477966 28314874 28314874 28314874 20477966 20477966 -8332186 20477966 -8332186 20477966 -8332186 20477966 -8332186 20477966 -8332186 20477966 -8332186 20477966 -8332186 20477966 -8332186 -8332186 -8332186 20477966 20477966 20477966 -8332186 20477966 20477966 20477966 20477966 28314874 28314874 28314874 28314874…

Example 3:

Input: 2576 -971723420 -456948624 -979289824 -771672307 750552854 -162976192 -319162847 337818927 277822756 712481543 -789835774 134635782 -551233433 -523609181 734373479 -767599155 -651010536 -589511697 363477646 -153602251 669243567 -112883009 -637375881 786360084 371246440 712703848 982027241 636338216 864313836 904175325 56699488 696415474 573174699 -691798234 148429593 -726484283 714464663 594360858 -156271850 -382922880 595989380 -962563347 507400790 -708068943 -863983233 -22651074 390122612 -929182053 275653116 687126535 803031959 -96576015 426316936 -484954885 374716828 -48566130 -582224353 962270696 764148638 -102167406 -859580286 -943263434 -432000197 185995028 661188836 -390240943 48233317 -411505432 -73364432 -467931194 350768323 628424633 733254239 923107628 -684037606 -673572202 701…
Output: -971723420 -971723420 -971723420 -971723420 -771672307 -771672307 -456948624 -456948624 -319162847 -319162847 -319162847 -319162847 -319162847 -456948624 -319162847 -456948624 -456948624 -523609181 -456948624 -456948624 -319162847 -319162847 -319162847 -319162847 -162976192 -162976192 -153602251 -153602251 -112883009 -112883009 56699488 56699488 134635782 56699488 134635782 56699488 134635782 134635782 134635782 56699488 134635782 56699488 134635782 56699488 56699488 -22651074 56699488 -22651074 56699488 56699488 134635782 56699488 134635782 56699488 134635782 56699488 56699488 56699488 134635782 56699488 56699488 -22651074 -22651074 -22651074 56699488 -22651074 48233317 -22651074 -22651074 -48566130 -22651074 -22651074 48233317 48233317 48233317 -22651074 48233317 -22651074 48233317 -2265…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Middle So Far at Firewatch - MEDIUM Coding Problem | CodeTikki