CT57412

The Middle So Far at Needlepoint

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Nina inherited the dairy at the pine barrens of Needlepoint 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: 2177 -356063874 689612859 -128093750 -144315471 958652365 498926253 153823712 871350230 174456085 -215637896 13078790 496092891 -155511873 722605902 535594499 532749552 673880854 251887579 -386496919 -737623672 -88374120 406205751 321678699 -856603088 514866201 68936252 454231948 -629979025 246402013 483623767 -944746812 290521995 329353156 -218455266 -121612683 998073984 -505337959 834859692 235299349 -244486895 -93983074 -663419789 -860213801 -621112189 -941249376 570788982 -510153593 529916187 -946768467 197904592 662262886 811051707 -708476365 89616619 748762244 96554726 -655035811 688332530 -965320330 -930835175 -297002501 732463781 195351895 801350042 -454536076 902919613 396800465 33082876 167538779 635855209 -34771144 -687639608 275609520 590655220 52822691 -48397276 477328010 -980…
Output: -356063874 -356063874 -128093750 -144315471 -128093750 -128093750 153823712 153823712 174456085 153823712 153823712 153823712 153823712 153823712 174456085 174456085 496092891 251887579 251887579 174456085 174456085 174456085 251887579 174456085 251887579 174456085 251887579 174456085 246402013 246402013 246402013 246402013 251887579 246402013 246402013 246402013 246402013 246402013 246402013 235299349 235299349 174456085 174456085 153823712 153823712 153823712 153823712 153823712 153823712 153823712 174456085 174456085 174456085 153823712 174456085 153823712 153823712 153823712 153823712 96554726 96554726 96554726 153823712 153823712 153823712 153823712 174456085 153823712 167538779 167538779 167538779 153823712 167538779 167538779 167538779 153823712 167538779 153823712 153823712 1410495…

Example 2:

Input: 228 -675110742 707272295 621030890 636071907 927941358 488777730 -761546420 688771650 -711370677 332138404 -472497597 -720086550 -145611139 105258672 488953458 -578195592 -63857754 -182197875 980081425 -394362863 637695605 388995835 -712107960 -80988641 -880168994 301047256 729708402 -323926463 678688459 615779561 162094996 104860079 -979951627 -567135379 -834086811 305838096 -439220953 -149334918 -773009330 75551732 -200457327 -641006597 614716347 341983318 -268101362 582854101 856025481 188942617 -556815200 459467673 -149691950 629415062 -445991051 34701367 459162743 140507963 982705397 -276664442 -476002758 -759463829 191883733 -104507658 950770700 -223537833 -936432595 -411351090 13941300 629351331 936854001 255881772 635584049 465369373 567907876 -628134454 779898363 308484117 4687034…
Output: -675110742 -675110742 621030890 621030890 636071907 621030890 621030890 621030890 621030890 488777730 488777730 332138404 332138404 105258672 332138404 105258672 105258672 -63857754 105258672 -63857754 105258672 105258672 105258672 -63857754 -63857754 -63857754 105258672 -63857754 105258672 105258672 162094996 105258672 105258672 104860079 104860079 104860079 104860079 -63857754 -63857754 -63857754 -63857754 -80988641 -63857754 -63857754 -63857754 -63857754 75551732 75551732 75551732 75551732 75551732 75551732 75551732 34701367 75551732 75551732 104860079 75551732 75551732 34701367 75551732 34701367 75551732 34701367 34701367 -63857754 13941300 13941300 34701367 34701367 75551732 75551732 104860079 75551732 104860079 104860079 104860079 75551732 75551732 46870345 75551732 75551732 75551732…

Example 3:

Input: 2894 156940497 -571189581 426315139 302812953 -963642489 -160171144 223476558 -858014043 528929804 -12246622 428577707 11220175 576260146 412379602 -73608024 -422230207 448949508 651300690 369294878 284760440 628146209 667935203 870839839 120767970 -961495136 534157570 338842742 -466601170 966618464 378043716 166016346 375089224 532533309 519561601 8853240 30515097 -542504425 792148715 988944697 770338847 -397804530 184931765 -972933499 936730688 392494860 500385943 -189607172 -667083730 289996693 76296419 217329010 -718346182 -598454030 361372702 -419216871 -207741273 459360966 -386148559 945579224 -140163501 -110751038 -731447554 -354109428 11021614 -488135945 613270226 266632199 -662882793 873791061 -683099348 872284907 767655061 630400392 -723145417 643076466 85107434 -27508315 -992467…
Output: 156940497 -571189581 156940497 156940497 156940497 -160171144 156940497 -160171144 156940497 -12246622 156940497 11220175 156940497 156940497 156940497 11220175 156940497 156940497 223476558 223476558 284760440 284760440 302812953 284760440 284760440 284760440 302812953 284760440 302812953 302812953 302812953 302812953 338842742 338842742 338842742 302812953 302812953 302812953 338842742 338842742 338842742 302812953 302812953 302812953 338842742 338842742 338842742 302812953 302812953 289996693 289996693 284760440 284760440 284760440 284760440 223476558 284760440 223476558 284760440 223476558 223476558 217329010 217329010 184931765 184931765 184931765 217329010 184931765 217329010 184931765 217329010 217329010 223476558 217329010 223476558 217329010 217329010 184931765 213269790 184931765…

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 Needlepoint - MEDIUM Coding Problem | CodeTikki