CT59866

Notary and the Gleaming registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Notary inherited the loom house at the lotus ponds of Tranquil Basin along with its curious bookkeeping system for registers. 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: 3577 333320368 -593677107 983750671 -170655178 -723399369 530417589 735715215 -221984191 -516263780 612711675 13487486 -434735695 -200930435 253264253 637931773 -953793077 -869876234 75628906 -949916445 405006049 631759347 -924946298 80605227 -947096916 -822578862 -731172304 395172369 330700553 -359102703 -528934724 -58762318 -162228124 -714151778 970415542 748457943 -508960032 705983785 -41921732 821968182 969380332 -751670084 -310358575 -359933181 222470056 902281445 -310364393 -330705465 135531631 981569173 14959319 716989592 -939086579 -242362763 -251055209 947151466 763550641 231370872 892703896 -753264306 -912104813 70092741 -674391166 -508920096 -374259950 -302982029 -961211171 565191991 507584837 659860322 163482810 -469050340 824693337 751811461 102118412 942125473 506126737 -4371…
Output: 333320368 -593677107 333320368 -170655178 -170655178 -170655178 333320368 -170655178 -170655178 -170655178 13487486 -170655178 -170655178 -170655178 13487486 -170655178 -170655178 -170655178 -170655178 -170655178 13487486 -170655178 13487486 -170655178 -170655178 -200930435 -170655178 -170655178 -170655178 -200930435 -170655178 -170655178 -170655178 -170655178 -162228124 -170655178 -162228124 -162228124 -58762318 -58762318 -58762318 -162228124 -162228124 -162228124 -58762318 -162228124 -162228124 -162228124 -58762318 -58762318 -41921732 -58762318 -58762318 -162228124 -58762318 -58762318 -41921732 -41921732 -41921732 -58762318 -41921732 -58762318 -58762318 -162228124 -162228124 -170655178 -162228124 -162228124 -58762318 -58762318 -58762318 -58762318 -41921732 -41921732 13487486 13487486 134…

Example 2:

Input: 133 -897447390 -830133173 233008856 -173910421 889859238 -901424283 -836375261 328667485 -464877946 894488737 748647914 -869691325 88599064 796921560 612488960 -667108824 -412122986 -983600661 417399468 -622803063 -298920604 -667399674 578616802 441701514 761901130 -217040885 101680285 -635261557 619276927 458450885 -394133149 773043766 903924747 -911347177 -566592529 -622302819 -689956443 -246238226 -280236028 606581380 667253639 158628074 -203261066 -961159870 46393706 490045182 862205921 510685764 953062912 -602942510 608602406 598529388 942665436 -192168893 -387804708 -553347397 963369130 -745481330 45748819 -392579719 284914110 337383074 966074704 392564104 669467548 477414618 797413301 -642230640 89157547 -816084435 569985122 410397756 -825406369 698738910 -587195748 413952146 -75703…
Output: -897447390 -897447390 -830133173 -830133173 -173910421 -830133173 -830133173 -830133173 -464877946 -464877946 -173910421 -464877946 -173910421 -173910421 88599064 -173910421 -173910421 -412122986 -173910421 -412122986 -298920604 -412122986 -298920604 -298920604 -173910421 -217040885 -173910421 -217040885 -173910421 -173910421 -173910421 -173910421 88599064 -173910421 -173910421 -217040885 -217040885 -246238226 -246238226 -246238226 -217040885 -217040885 -203261066 -217040885 -203261066 -203261066 -173910421 -173910421 46393706 -173910421 46393706 46393706 88599064 46393706 46393706 -173910421 46393706 -173910421 45748819 -173910421 45748819 45748819 46393706 46393706 88599064 88599064 101680285 88599064 89157547 88599064 89157547 89157547 89157547 89157547 89157547 89157547 89157547 885990…

Example 3:

Input: 2371 493946270 18798565 450988236 -332295423 580638561 -886510465 44662888 435190746 643032655 541519561 -637421763 -209791607 -341966551 366163328 -860213679 -293387027 666735758 501309916 844643444 -223350287 437730147 -912744159 -167762572 243786554 240825358 -74567996 298548600 -98814658 -80384897 78753278 -539647736 918985747 244759067 22255641 -82312059 -27507419 -663065820 -352930666 -329047997 -492239687 -275430357 -884099957 -611461665 -531406315 -328977250 836096691 -649605577 30577093 -171411934 -911884665 655313044 902932685 173330422 49428474 32618618 214249335 -90965585 -492945457 624105008 -29275218 972969496 69834614 -905471366 625447557 -460684087 -507674947 968340117 -904469231 525139379 479419482 -851709336 -41378726 335189748 257799010 -364118246 -980962972 194394740 28…
Output: 493946270 18798565 450988236 18798565 450988236 18798565 44662888 44662888 435190746 435190746 435190746 44662888 44662888 44662888 44662888 18798565 44662888 44662888 366163328 44662888 366163328 44662888 44662888 44662888 240825358 44662888 240825358 44662888 44662888 44662888 44662888 44662888 78753278 44662888 44662888 22255641 22255641 18798565 18798565 -27507419 -27507419 -74567996 -74567996 -80384897 -80384897 -80384897 -80384897 -80384897 -80384897 -82312059 -80384897 -80384897 -74567996 -74567996 -27507419 -27507419 -27507419 -74567996 -27507419 -29275218 -27507419 -27507419 -27507419 -27507419 -27507419 -29275218 -27507419 -29275218 -27507419 -27507419 -27507419 -29275218 -27507419 -27507419 -27507419 -29275218 -27507419 -27507419 -19832313 -19832313 18798565 18798565 18798565 -1…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Notary and the Gleaming registers - MEDIUM Coding Problem | CodeTikki