CT63306

The Middle So Far of Needlepoint

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the pine barrens of Needlepoint as Jatin unrolls the day's manifest of beacons. The tally will decide the next shipment. 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: 3783 784428080 -193120407 -858514381 -997948375 -844219571 938722792 -722999300 -584067867 881576513 -70056211 488213942 -910763147 751964039 905244914 -172870692 -244605412 -51625085 122953505 1268254 195552962 52468480 717425909 -955324489 47767115 -292147447 -552659141 761507427 -144866517 490746259 -264888880 -398992791 341125777 558283810 648675467 452530325 -662073113 146262789 695868159 863564734 -890506309 -717132826 -495774010 202381026 799159586 -873302424 -891560854 139943530 -794248827 45572186 884086313 -788209228 -193982328 -659426700 870634243 -731819094 -979872022 594769131 -557330413 819947116 -436116337 912182540 275682449 -68001245 -42577114 416675683 459918542 871214336 -461871162 648899899 844450228 998682144 450385867 -9680629 -715176347 -931484912 399911584 214074036…
Output: 784428080 -193120407 -193120407 -858514381 -844219571 -844219571 -722999300 -722999300 -584067867 -584067867 -193120407 -584067867 -193120407 -193120407 -172870692 -193120407 -172870692 -172870692 -70056211 -70056211 -51625085 -51625085 -51625085 -51625085 -51625085 -70056211 -51625085 -70056211 -51625085 -70056211 -70056211 -70056211 -51625085 -51625085 1268254 -51625085 1268254 1268254 47767115 1268254 1268254 -51625085 1268254 1268254 1268254 -51625085 1268254 -51625085 1268254 1268254 1268254 -51625085 -51625085 -51625085 -51625085 -70056211 -51625085 -70056211 -51625085 -70056211 -51625085 -51625085 -51625085 -51625085 -42577114 -42577114 1268254 -42577114 1268254 1268254 45572186 45572186 45572186 1268254 1268254 1268254 45572186 45572186 45572186 45572186 47767115 47767115 47767115 …

Example 2:

Input: 154 537743334 351477087 713611470 786971477 -369487053 -342583239 551528676 -995304837 539441995 40758146 834172742 -61050870 495300985 -526853743 952055812 425701264 -989284174 307001945 -652364366 507403858 -49802908 57513237 -2032761 752289749 81094735 595153072 206766182 393368068 -197450492 -223953048 -795350799 -31100483 91308177 877383629 478032190 -966653966 390339554 189227727 951275541 260663259 668180038 353228835 -767675197 347252630 -34045964 -662657553 -221460199 -376427965 915583085 -28656638 -481865178 357586208 764194712 41716536 632931730 444841234 -599260837 523098309 753520263 897165692 418600599 -113581631 207966862 -734294154 -489089397 227667707 245588018 -623608774 -716333541 -998643128 -622828145 489253989 853599761 -713945761 628403277 443536521 -254562854 -234599…
Output: 537743334 351477087 537743334 537743334 537743334 351477087 537743334 351477087 537743334 351477087 537743334 351477087 495300985 351477087 495300985 425701264 425701264 351477087 351477087 351477087 351477087 307001945 307001945 307001945 307001945 307001945 307001945 307001945 307001945 206766182 206766182 81094735 91308177 91308177 206766182 91308177 206766182 189227727 206766182 206766182 260663259 260663259 260663259 260663259 260663259 206766182 206766182 189227727 206766182 189227727 189227727 189227727 206766182 189227727 206766182 206766182 206766182 206766182 260663259 260663259 307001945 260663259 260663259 207966862 207966862 207966862 227667707 207966862 207966862 206766182 206766182 206766182 207966862 206766182 207966862 207966862 207966862 206766182 207966862 206766182 2067…

Example 3:

Input: 2781 281531768 749324407 745414805 -865356124 -558891798 -286865105 328543222 262346664 76677677 -894339315 193581678 -368087386 758006475 793715564 -848479225 -828033423 218540016 -830337413 151940068 -661694498 -600582662 689739409 -372555191 443741220 598722757 893936449 884560587 495771350 282770129 58459053 673309255 962568557 396009769 -874960620 -754436030 -719540115 -119902605 -654826962 -368474544 442284262 -6679192 652242931 -340706928 395774060 -572483827 -325707619 -994110320 -911913721 323508555 -57974817 -998097790 829457412 -15966721 517939726 311500431 -431324314 -159208607 511038297 457941164 304758348 914402527 -700462432 476902593 432993324 -436554179 -573609429 -531261640 -532273718 149987578 -915008851 -342173904 -669515946 -188191705 -352413255 -453310567 -298225085 3…
Output: 281531768 281531768 745414805 281531768 281531768 -286865105 281531768 262346664 262346664 76677677 193581678 76677677 193581678 193581678 193581678 76677677 193581678 76677677 151940068 76677677 76677677 76677677 76677677 76677677 151940068 151940068 193581678 193581678 218540016 193581678 218540016 218540016 262346664 218540016 218540016 193581678 193581678 151940068 151940068 151940068 151940068 151940068 151940068 151940068 151940068 76677677 76677677 58459053 76677677 58459053 58459053 58459053 58459053 58459053 76677677 58459053 58459053 58459053 76677677 76677677 151940068 76677677 151940068 151940068 151940068 76677677 76677677 58459053 76677677 58459053 58459053 -6679192 -6679192 -15966721 -15966721 -57974817 -15966721 -57974817 -57974817 -57974817 -15966721 -57974817 -15966721 -1…

Constraints:

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

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