RMID - Running Median
You will be given some integers in non decreasing order and each time the median is queried you have to report and remove it. Take the smaller element as median in case of even elements.
Input
The input contains many test cases. Read until End Of File.
Each test case contains n (n ≤ 100000) positive integers in non-decreasing order, along with m queries indicated by -1, all on separate lines. (See the example.)
For a query, print the current median on a single line and remove it from the list.
Each test case ends with 0 on a single line, and two test cases will be separated by an empty line. All integers are guaranteed to fit in a signed 32-bit container. A query can only occur if the list is non-empty.
Output
For each test case output m lines containing the answers to the corresponding queries. Print an empty line after each test case.
Example
Input: 1 2 3 4 -1 -1 5 6 7 -1 0 2 3 -1 0 Output: 2 3 5 2
hide comments
vl4deee11:
2024-03-28 03:42:56
AC with two heaps :-) |
|
gorr__:
2021-07-27 15:53:00
pbds+cin/cout with fast i/o =>TLE
|
|
Shubham Jadhav:
2020-07-04 14:23:11
use fast i/o |
|
black_shroud:
2020-06-03 10:30:29
i my opinion linked list is best data structure here due to o(1) deletion property |
|
morasiu:
2020-05-11 11:07:00
In C# EOF is when Console.ReadLine() returns null |
|
vinty:
2020-04-24 16:00:28
How to know when it is end of file and we need to stop taking input? |
|
akashthegreat:
2019-08-28 12:51:27
I got TLE on using cout but got AC on using printf.
|
|
ankit_mnnit:
2018-10-09 19:13:58
This question can be easily done by using vector and by using printf and scanf. |
|
be1035016:
2018-06-17 15:31:45
first time implemented linked list on an online judge:) |
|
aman_sachin200:
2018-05-30 21:30:38
BIT+Binary Search=AC!!:)Be careful with input format!! |
Added by: | jayant mukherji |
Date: | 2013-07-12 |
Time limit: | 0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |