CT64694

Ulmar and the Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the caldera rim of Firewatch close for winter, Ulmar must finish the ledgers ledger - one figure at a time. 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: 1628 -141267423 495977365 350197846 -593862948 -283541221 491926006 430703889 330092190 825633487 -306302140 708258996 795556681 -792970907 -468673618 -854102572 286532138 482908363 -249386739 274453040 -99863584 553754525 -681884195 152643183 801169895 39720526 97441667 479782343 -622016046 -255572712 -705258818 13507995 -117396265 -60242533 694017652 520831677 -304859421 -55719196 -474248662 -370972492 -850493877 700773055 -987160943 555195023 -634949580 -348477586 -952235952 277033855 -374120258 75380346 -173635791 256024618 -977994983 83952579 -69763945 -226096969 -431755892 -683541780 584234235 834930237 950776580 -918042086 -489474884 -16102674 -703117331 405977100 -563274154 -415003578 193442701 -645169815 -355630484 -394248657 -594480251 -933773207 -769735415 146907963 140987425 74…
Output: -141267423 -141267423 350197846 -141267423 -141267423 -141267423 350197846 330092190 350197846 330092190 350197846 350197846 350197846 330092190 330092190 286532138 330092190 286532138 286532138 274453040 286532138 274453040 274453040 274453040 274453040 152643183 274453040 152643183 152643183 97441667 97441667 39720526 39720526 39720526 97441667 39720526 39720526 13507995 13507995 -55719196 13507995 -55719196 13507995 -55719196 -55719196 -60242533 -55719196 -60242533 -55719196 -60242533 -55719196 -60242533 -55719196 -60242533 -60242533 -69763945 -69763945 -69763945 -60242533 -60242533 -60242533 -69763945 -60242533 -69763945 -60242533 -69763945 -69763945 -69763945 -69763945 -99863584 -99863584 -117396265 -117396265 -141267423 -117396265 -117396265 -99863584 -99863584 -99863584 -117396265 -…

Example 2:

Input: 2242 -843664825 -939157190 696814830 713228407 246815475 332370607 606617118 -928390596 -747827255 -279542589 922096608 95483824 202619602 983519437 -138561281 -987629803 -742579104 531770063 754826509 -677937265 -266333842 390437449 -258701715 387835106 -299498113 -327022713 -596490053 887629251 782983177 831466565 -68889630 788242335 208032771 -705240668 221830690 141803068 -1420925 -412245788 -917800448 273364128 -685909955 668096283 -222980084 -890270101 -887261738 65821291 53882816 -61367322 164955296 -575091855 570742849 989387135 425637682 959537398 -255601744 -692837980 662860750 -114102709 -174433918 707321071 -465729055 -818588909 -20517493 -618640309 252834847 601336456 481344517 36536111 715462418 32433659 -349433182 845996942 888580062 -538234614 26005977 -293239518 239770519 …
Output: -843664825 -939157190 -843664825 -843664825 246815475 246815475 332370607 246815475 246815475 -279542589 246815475 95483824 202619602 202619602 202619602 95483824 95483824 95483824 202619602 95483824 95483824 95483824 95483824 95483824 95483824 -138561281 -138561281 -138561281 95483824 95483824 95483824 95483824 202619602 95483824 202619602 141803068 141803068 95483824 95483824 95483824 95483824 95483824 95483824 -1420925 -1420925 -1420925 53882816 -1420925 53882816 -1420925 53882816 53882816 65821291 65821291 65821291 53882816 65821291 53882816 53882816 53882816 53882816 -1420925 -1420925 -20517493 -1420925 -1420925 53882816 36536111 53882816 36536111 36536111 36536111 53882816 36536111 36536111 32433659 36536111 32433659 32433659 26005977 32433659 26005977 32433659 26005977 26005977 2600…

Example 3:

Input: 2996 -413357923 868074448 -980690416 989036235 -29854525 221321485 -402946240 617335243 304653271 -262910003 -220454449 895250929 348327660 487721926 -629755410 1608605 -422879219 14012726 981503010 -819205724 -541017139 -731236714 261237619 980410155 -842582766 907744829 -368848640 -510854957 -903889865 -741723293 538359060 -140037408 249819608 191180615 -357499040 768185395 66974068 556713837 -716069843 -594529162 -159602901 483888524 -814638397 928697701 -34218634 -854798161 -437590674 -829575944 922474968 -495472199 -914380093 -775856493 246979814 -483992595 622237494 -767259453 816671639 -180415120 5297524 561332393 404796470 125929571 -162084458 371958629 -647492018 454648693 -954273084 -432091573 684404821 97106817 425268340 694166944 -597199825 292459699 139184770 429987778 -459104…
Output: -413357923 -413357923 -413357923 -413357923 -29854525 -29854525 -29854525 -29854525 221321485 -29854525 -29854525 -29854525 221321485 221321485 221321485 1608605 1608605 1608605 14012726 1608605 1608605 -29854525 1608605 1608605 1608605 1608605 1608605 -29854525 -29854525 -220454449 -29854525 -140037408 -29854525 -29854525 -29854525 -29854525 1608605 1608605 1608605 -29854525 -29854525 -29854525 -29854525 -29854525 -29854525 -34218634 -34218634 -140037408 -34218634 -140037408 -140037408 -159602901 -140037408 -159602901 -140037408 -159602901 -140037408 -159602901 -140037408 -140037408 -34218634 -34218634 -34218634 -34218634 -34218634 -34218634 -34218634 -140037408 -34218634 -34218634 -29854525 -29854525 -29854525 -29854525 1608605 1608605 1608605 -29854525 1608605 -29854525 -29854525 -34218…

Constraints:

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

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