CT64948

Secret registers Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the herring shoals of Silverfin opens only for a perfect tally of registers. Odin means to find out. 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: 3993 334444586 -87254279 209479014 755924901 780962580 749528971 -549415865 -643158536 351357578 517635099 -312416624 621473190 448786376 85603184 192686203 416190688 -77449150 987777305 -505073625 266321461 -960500457 590740540 -133147106 877605545 -129974328 -669227453 820084017 104178668 -92076239 87661633 -587268637 -471157570 911995663 -678652141 -443569999 -222707786 285360727 523885468 325073905 634084055 578072979 -718787268 -601756932 -791059351 848470603 -235843999 -613650726 522466285 388214884 -376280268 -436319377 -690515330 120400010 809731129 133732518 -262859933 -192079211 -514385480 64402675 369733053 -504912567 211089431 -454788234 -662594072 -336779027 945711265 -459052211 -225088811 -879815646 236478862 93356938 -8358081 -459807975 158407342 -217373503 -149065094 -47556…
Output: 334444586 -87254279 209479014 209479014 334444586 334444586 334444586 209479014 334444586 334444586 334444586 334444586 351357578 334444586 334444586 334444586 334444586 334444586 334444586 266321461 266321461 266321461 266321461 266321461 266321461 209479014 266321461 209479014 209479014 192686203 192686203 104178668 192686203 104178668 104178668 87661633 104178668 104178668 192686203 192686203 209479014 192686203 192686203 104178668 192686203 104178668 104178668 104178668 192686203 104178668 104178668 87661633 104178668 104178668 120400010 104178668 104178668 87661633 87661633 87661633 87661633 87661633 87661633 85603184 85603184 85603184 85603184 64402675 64402675 64402675 85603184 64402675 64402675 64402675 64402675 -8358081 -8358081 -8358081 -8358081 -77449150 -8358081 -8358081 514466…

Example 2:

Input: 2240 -900528726 -106242768 -550095886 -71161564 -391371897 -41078903 -515868436 -145050391 625135168 941259697 -824603285 525006263 -445399341 -14361494 -743862250 -169006732 -627457835 853031720 -32000515 -801786472 745272020 -764304312 732543076 612230498 -16653234 -982727828 668100170 171260776 4875797 -837176435 -621952419 -167598084 -632281239 -486106996 -25531781 -108914362 -928464520 613107122 38959884 -310276405 65689883 453778450 -180055402 471536529 -293151797 944900025 -506550049 847145173 -106834323 657461398 641580115 -985691234 83226327 -164181827 290228877 91097810 -792199121 878655917 233146108 -137275273 -84580237 579363907 76672542 234105541 -233540816 737594025 527310952 -321290287 -992069955 -40839697 35032584 -542382799 470204698 -812826453 149684961 -700647648 -171337…
Output: -900528726 -900528726 -550095886 -550095886 -391371897 -391371897 -391371897 -391371897 -145050391 -145050391 -145050391 -145050391 -145050391 -145050391 -145050391 -169006732 -169006732 -169006732 -145050391 -169006732 -145050391 -169006732 -145050391 -145050391 -106242768 -145050391 -106242768 -106242768 -71161564 -106242768 -106242768 -145050391 -145050391 -167598084 -145050391 -145050391 -145050391 -145050391 -108914362 -145050391 -108914362 -108914362 -108914362 -108914362 -108914362 -108914362 -108914362 -108914362 -106834323 -106834323 -106242768 -106834323 -106242768 -106834323 -106242768 -106242768 -106242768 -106242768 -71161564 -106242768 -84580237 -84580237 -71161564 -71161564 -71161564 -71161564 -41078903 -71161564 -71161564 -71161564 -41078903 -71161564 -41078903 -71161564 -4…

Example 3:

Input: 553 -873200973 352632900 -617926185 -410748592 400341610 349543099 4999556 -691651469 -937971060 156671693 -845513325 279744954 487887188 758911441 326345986 -180929069 541204409 985020343 706836171 -309626593 -562994823 -336541915 -758357373 866234802 224162896 -989977862 -654676863 -337075020 -499775486 -211507006 -903471467 615551530 -622448178 -931356903 365885963 -325105201 -900432898 215417640 -163627863 490493647 337020582 -242404397 -402459996 -278504121 157388633 312387126 879042393 -554865139 -710546569 368168866 -351648350 196627182 -833430325 -944159586 250832155 854096388 -609731186 -604047008 -509079897 319588900 3155487 -500646946 438761207 930652541 -351383406 327558168 297304475 -314652139 -933432399 78996289 -550667307 -339048634 -844254230 -126699342 -256618381 780790961…
Output: -873200973 -873200973 -617926185 -617926185 -410748592 -410748592 4999556 -410748592 -410748592 -410748592 -410748592 -410748592 4999556 4999556 156671693 4999556 156671693 156671693 279744954 156671693 156671693 4999556 4999556 4999556 156671693 4999556 4999556 -180929069 -180929069 -211507006 -211507006 -211507006 -211507006 -309626593 -211507006 -309626593 -309626593 -309626593 -211507006 -211507006 -180929069 -211507006 -211507006 -242404397 -211507006 -211507006 -180929069 -211507006 -211507006 -211507006 -211507006 -211507006 -211507006 -242404397 -211507006 -211507006 -211507006 -242404397 -242404397 -242404397 -211507006 -242404397 -211507006 -211507006 -211507006 -211507006 -180929069 -211507006 -211507006 -211507006 -211507006 -242404397 -242404397 -242404397 -242404397 -24240439…

Constraints:

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

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