CT59225

The Cinderline Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The log keeper Petr has been asked to assign crews to the morning shifts. On the desk lies a long table of beacons readings. 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: 3688 -982245263 -782176256 766628605 365555099 141300306 -94530325 180772598 -244668612 -795994133 933304982 -974102764 468979868 -767187064 -897769979 276257037 568073134 898870266 306547236 305645919 721741899 610394327 285378673 -337914937 822066114 -350898369 333597390 -950166330 -7554216 659419308 -969805222 -842890413 348284435 826591053 737867743 -358966618 715851746 -411423315 676872773 -943117897 131357810 -968048401 445303169 718938384 726512956 365314331 -390004913 474475096 -933690765 47270652 -431376424 -894170783 -270662129 51893396 144275678 -348329536 960019298 -537098204 427627297 995877138 -491056033 -396839278 -716926247 -443004092 -756543750 803541171 -991699049 -509323438 600784720 379234337 902757746 609706571 -767487230 643930059 703556185 -295274765 -163014695 -6532…
Output: -982245263 -982245263 -782176256 -782176256 141300306 -94530325 141300306 -94530325 -94530325 -94530325 -94530325 -94530325 -94530325 -244668612 -94530325 -94530325 141300306 141300306 180772598 180772598 276257037 276257037 276257037 276257037 276257037 276257037 276257037 180772598 276257037 180772598 180772598 180772598 276257037 276257037 276257037 276257037 276257037 276257037 276257037 180772598 180772598 180772598 276257037 276257037 285378673 276257037 285378673 276257037 276257037 180772598 180772598 141300306 141300306 141300306 141300306 141300306 141300306 141300306 144275678 141300306 141300306 131357810 131357810 51893396 131357810 51893396 51893396 51893396 131357810 131357810 141300306 131357810 141300306 141300306 141300306 131357810 131357810 51893396 131357810 131357810 …

Example 2:

Input: 20 723193252 -56919754 700762685 924592020 -836118469 953062989 -440053186 495128591 990692088 730312380 490606197 -313769066 -294035925 -741210942 718461272 261218834 39842650 293327609 644992159 720508837
Output: 723193252 -56919754 700762685 700762685 700762685 700762685 700762685 495128591 700762685 700762685 700762685 495128591 495128591 490606197 495128591 490606197 490606197 293327609 490606197 490606197

Example 3:

Input: 3008 40827551 271246998 -37440393 -162430284 237025172 -765855434 -955660164 923666585 224278241 -829734733 -352169350 -552711000 -228863807 848921479 -808608026 677170451 525659588 882937412 -325777596 296727860 559000634 -332288799 883281790 502709905 258427126 -699541103 594871240 455990256 414198562 151462957 404326794 -737861737 -441209800 293910285 -655232565 -802899896 700632797 514895 -480264552 951500967 -940371667 725162279 -832263200 -999610369 447480401 -963429613 931034308 592448853 -380358935 160705414 100236405 903260113 -758930193 726820375 685762316 588431934 -872346899 170177747 -398221965 203334903 -663934204 581046280 -602539794 -739095253 -633185392 641243880 -984140274 481097170 136450663 -274481655 804893478 400746039 -541806725 -681378492 49546589 -350075649 1587006…
Output: 40827551 40827551 40827551 -37440393 40827551 -37440393 -37440393 -37440393 40827551 -37440393 -37440393 -162430284 -162430284 -162430284 -162430284 -162430284 -37440393 -37440393 -37440393 -37440393 40827551 -37440393 40827551 40827551 224278241 40827551 224278241 224278241 237025172 224278241 237025172 224278241 224278241 224278241 224278241 151462957 224278241 151462957 151462957 151462957 151462957 151462957 151462957 40827551 151462957 40827551 151462957 151462957 151462957 151462957 151462957 151462957 151462957 151462957 160705414 160705414 160705414 160705414 160705414 160705414 160705414 160705414 160705414 151462957 151462957 151462957 151462957 151462957 151462957 136450663 151462957 151462957 151462957 136450663 136450663 100236405 100236405 69946309 69946309 69946309 69946309 …

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Cinderline Middle So Far - MEDIUM Coding Problem | CodeTikki