| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14821 | DS HW3 Median Round-trip Time with Continuous Ping |
|
Description
The "round-trip time (RTT)" between two hosts (i.e. computers) is the total time needed for a message to travel from the source host to the destination host, and then back to the source host. This information is useful for preliminary network performance diagnosis to know the minimum time needed for any communication, or if any communication is possible at all between the two hosts.
RTTs are commonly measured using the program "ping". Ping periodically sends a request to a remote host to trigger a response back. It also times the delay between sending the request and receiving the response, where the delay is the estimated RTT between the local and remote hosts. To get an overall sense of the network condition, ping also computes and outputs the current median of all estimated RTTs that the program has observed since the start of execution.
You are to write a C/C++ program that imitates ping's ability to compute the median estimated RTT for a stream of estimated RTTs. Your program should take in RTTs (in ms) and a command med. Upon getting the command med, your program should output the current median RTT based on all RTTs that your program have taken in before the command. To make things easier, each RTT will be an integer, storable in an int variable. Additionally, you should use C division when computing the 2-RTT average with even number of RTTs. E.g. median for RTTs 2 5 3 4 should be (3+4)/2 = 3.
Your program MAY use C++ standard library headers.
HINT: you should aim to achieve constant time complexity for median computation.
Input
A new line containing the number of RTTs and commands to be read in (M, 0 < M <= 5 * 10^7). The following M lines then either (1) contains a single RTT (always non-negative) or (2) contains a med command.
You can assume that the med command will only appear after there is at least one RTT.
Output
The medians outputted by med, one outcome per line. Each outcome should be newline ('\n') terminated.
Note: since the input size M can be as large as 5 × 10^7, you must enable fast C++ I/O to avoid timeouts:
ios::sync_with_stdio(false);
cin.tie(0);