CT58597

The Middle So Far of Whitewick

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Peddler inherited the foundry at the cotton rows of Whitewick along with its curious bookkeeping system for beacons. Time to make sense of it. 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: 3793 991098780 653737553 333567701 646414972 -254381037 -996052850 -454330771 776022207 -730530264 833545843 97422584 386892577 -885166907 201476491 -474715744 -149283706 -216560953 -518902777 41032481 867132591 -437244281 392325275 990777580 709314554 -67981283 988858796 -468399 -368440841 903302650 831975801 913083685 -203855862 513904861 748439046 -890235967 791855015 838499896 899629454 -596453676 597134337 45345972 660715658 -357565351 407053507 -786991482 -309257402 -277202133 -326924279 757206865 -247488398 788171216 794098614 -105389045 390667923 571925149 621521329 743660694 -94234245 -523404947 948991761 -490374725 455247675 -665796303 627406446 -928342811 -535094562 530614155 -665992051 -770750497 826356863 -172558804 404430629 -989979728 -251059978 439504459 271783876 -59208255…
Output: 991098780 653737553 653737553 646414972 646414972 333567701 333567701 333567701 333567701 333567701 333567701 333567701 333567701 201476491 201476491 97422584 97422584 -149283706 41032481 41032481 41032481 41032481 97422584 97422584 97422584 97422584 97422584 41032481 97422584 97422584 201476491 97422584 201476491 201476491 201476491 201476491 333567701 333567701 333567701 333567701 333567701 333567701 333567701 333567701 333567701 201476491 201476491 97422584 201476491 97422584 201476491 201476491 201476491 201476491 333567701 333567701 386892577 333567701 333567701 333567701 333567701 333567701 333567701 333567701 333567701 201476491 333567701 201476491 201476491 201476491 201476491 201476491 201476491 97422584 201476491 201476491 201476491 201476491 201476491 201476491 201476491 9742258…

Example 2:

Input: 3897 -400523447 -926411813 -516560470 -582979611 -351999941 400487149 967680167 -27471560 -146666890 -475645338 -378469702 307764786 267129301 668058515 -613408004 70717808 -24333352 202094134 345850620 -754236184 397826961 -461260861 81384060 -991487057 78556793 724165663 -594146493 521996322 -122281865 662039671 -809081192 -482923890 415373180 -821956326 -683091614 689799596 -791708610 -317579561 399477844 -390253032 -640890650 -812155289 822059040 -499682285 -301568773 128882411 -816297413 708480434 942094616 415276113 -74744577 -981343948 864747164 -956978662 -850207440 52785445 420386256 -663866581 835198495 -727957860 -695230221 249456971 947748075 495678035 -139426563 -206854881 114634788 618482740 97803503 220702434 583497571 114925556 -982962799 -850916376 88682070 657788136 38630…
Output: -400523447 -926411813 -516560470 -582979611 -516560470 -516560470 -400523447 -400523447 -351999941 -400523447 -378469702 -378469702 -351999941 -351999941 -351999941 -351999941 -146666890 -146666890 -27471560 -146666890 -27471560 -146666890 -27471560 -146666890 -27471560 -27471560 -27471560 -27471560 -27471560 -27471560 -27471560 -122281865 -27471560 -122281865 -122281865 -122281865 -122281865 -146666890 -122281865 -146666890 -146666890 -317579561 -146666890 -317579561 -301568773 -301568773 -301568773 -301568773 -146666890 -146666890 -122281865 -146666890 -122281865 -146666890 -146666890 -146666890 -122281865 -146666890 -122281865 -146666890 -146666890 -146666890 -122281865 -122281865 -122281865 -139426563 -122281865 -122281865 -74744577 -74744577 -27471560 -27471560 -27471560 -74744577 -27…

Example 3:

Input: 320 -291939990 -405093354 -678849682 72981682 535093081 244670859 881008000 923003393 849964612 -803398375 -449666051 -993176735 774315719 -570248254 -12011174 907846831 -161520012 -821672248 -66043429 897839884 965190123 -849516893 -693370516 -782441736 -971066469 27952112 -151999841 273757353 919967783 -979919928 302057069 -500595450 -494853607 53992903 -313045828 -808352573 -237436859 -148800101 -904801224 983627903 -996081204 976511424 -243883495 860875034 -598687639 365387640 -703256798 -511676027 674436872 652543581 855673769 -421416208 812537867 726788915 -793299676 164826667 867493311 -441312097 -375612159 -561026122 -433054005 -990968438 329706591 -141044990 988430500 40669068 -121685562 -548205608 -683742040 575691006 473222724 -49375578 454835472 -421392167 -774381812 417234796 …
Output: -291939990 -405093354 -405093354 -405093354 -291939990 -291939990 72981682 72981682 244670859 72981682 72981682 -291939990 72981682 -291939990 -12011174 -12011174 -12011174 -161520012 -66043429 -66043429 -12011174 -66043429 -66043429 -161520012 -161520012 -161520012 -151999841 -151999841 -66043429 -151999841 -66043429 -151999841 -151999841 -151999841 -151999841 -161520012 -161520012 -161520012 -161520012 -161520012 -161520012 -161520012 -161520012 -161520012 -161520012 -161520012 -161520012 -237436859 -161520012 -161520012 -151999841 -161520012 -151999841 -151999841 -151999841 -151999841 -148800101 -151999841 -151999841 -161520012 -161520012 -237436859 -161520012 -161520012 -151999841 -151999841 -148800101 -151999841 -151999841 -151999841 -148800101 -148800101 -141044990 -148800101 -148800…

Constraints:

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

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