CT58254

Opal Counts the beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the indigo vats of Bluehollow close for winter, Opal must finish the beacons 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: 2206 404907785 383854435 -81293155 -900131072 -71010161 -943480176 315367879 -507469449 527579951 -495692324 724025676 780338537 -152183749 -739227591 555925304 775222849 -569305849 -473585136 -318955518 -497128899 -471667809 -652966583 -664512811 500637592 653817922 -261794867 902118510 -642677811 699269928 -619286249 185013604 -135922113 215738397 -500255091 326355711 182875930 263241630 -924045537 -994073446 -159258475 -397872728 950234440 469799549 47259641 -880045418 775970143 -56130320 -804668164 160522554 82413397 -803315787 -926959699 241024652 -630143474 -921666988 -269748246 -681118324 391008436 398834481 -444685164 -109988478 778121080 -647080118 -676603318 -885563929 783904775 -483598649 167318648 4242992 -823981208 57343550 881787967 735297287 -351341091 745898685 725427970 10…
Output: 404907785 383854435 383854435 -81293155 -71010161 -81293155 -71010161 -81293155 -71010161 -81293155 -71010161 -71010161 -71010161 -81293155 -71010161 -71010161 -71010161 -81293155 -81293155 -152183749 -152183749 -318955518 -318955518 -318955518 -152183749 -261794867 -152183749 -261794867 -152183749 -261794867 -152183749 -152183749 -135922113 -152183749 -135922113 -135922113 -81293155 -135922113 -135922113 -152183749 -152183749 -152183749 -135922113 -135922113 -135922113 -135922113 -81293155 -135922113 -81293155 -81293155 -81293155 -135922113 -81293155 -135922113 -135922113 -152183749 -152183749 -152183749 -135922113 -152183749 -135922113 -135922113 -135922113 -152183749 -152183749 -152183749 -152183749 -152183749 -135922113 -152183749 -135922113 -135922113 -109988478 -135922113 -109988478 …

Example 2:

Input: 1406 -418498478 -172055350 196888535 -347017229 -748651486 -620641703 -932230111 918238905 -452709493 -872924553 -433510235 -54362733 -397356684 -134970418 842981662 -107343042 -857777670 905560640 -323782422 -210078295 -643431186 213760771 785495227 862690011 247246772 525772758 -934014454 215998105 -127413812 224768036 -120752814 172124133 666158502 365146365 -233333977 -725053222 332438756 62140439 532879336 -849722615 268173934 -498953846 991976605 387398892 522156804 -674114637 -905899073 486592712 -979212066 -897951348 -159566236 -351853668 39256177 664968234 949811745 -20176976 -249015688 -616877165 294507638 -663915579 9282437 -1176054 -771862934 -587280477 -405532836 659537854 -664464143 269514223 -201726900 -451951458 72204136 -514877096 -940278626 724147202 205559566 967016934 9…
Output: -418498478 -418498478 -172055350 -347017229 -347017229 -418498478 -418498478 -418498478 -418498478 -452709493 -433510235 -433510235 -418498478 -418498478 -397356684 -397356684 -397356684 -397356684 -347017229 -347017229 -347017229 -347017229 -323782422 -323782422 -210078295 -210078295 -210078295 -210078295 -172055350 -172055350 -134970418 -134970418 -127413812 -127413812 -127413812 -134970418 -127413812 -127413812 -120752814 -127413812 -120752814 -127413812 -120752814 -120752814 -107343042 -120752814 -120752814 -120752814 -120752814 -127413812 -127413812 -134970418 -127413812 -127413812 -120752814 -120752814 -120752814 -127413812 -120752814 -127413812 -120752814 -120752814 -120752814 -127413812 -127413812 -127413812 -127413812 -127413812 -127413812 -134970418 -127413812 -134970418 -1349704…

Example 3:

Input: 2758 953972705 275078759 -225460968 753630295 -264454067 -151016437 -764183192 540987711 579457414 -589249845 886431653 -124272167 -898963880 307059102 -800066281 889382304 -325319454 -704354245 -152828054 866547602 -274497680 -971361510 -562343427 101570518 871058750 185468610 -140630654 -495218781 22141520 -971762864 -159049343 386652204 769714109 -11123572 -59470285 -383025512 -467710700 -337246457 453863982 -114639832 -440745020 146596397 -133722563 662383133 365197365 -952148466 182943098 789055761 -792437378 112058470 -596980907 320084708 707403410 80644674 666626321 -623117762 432443998 -301438195 -457016050 133071967 -145314734 -156586951 917193736 786351620 48914368 -47682741 -525226138 280580355 -551957621 -56091345 -377697885 -222363989 -610482159 -867296990 331943083 -425477237…
Output: 953972705 275078759 275078759 275078759 275078759 -151016437 -151016437 -151016437 275078759 -151016437 275078759 -124272167 -124272167 -124272167 -124272167 -124272167 -124272167 -151016437 -151016437 -151016437 -151016437 -152828054 -152828054 -152828054 -151016437 -151016437 -140630654 -151016437 -140630654 -151016437 -151016437 -151016437 -140630654 -140630654 -124272167 -140630654 -140630654 -151016437 -140630654 -140630654 -140630654 -140630654 -133722563 -133722563 -124272167 -133722563 -124272167 -124272167 -124272167 -124272167 -124272167 -124272167 -114639832 -114639832 -59470285 -114639832 -59470285 -114639832 -114639832 -114639832 -114639832 -124272167 -114639832 -114639832 -59470285 -59470285 -59470285 -59470285 -59470285 -59470285 -59470285 -114639832 -114639832 -124272167 -1…

Constraints:

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

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