← 返回 amazon 的题目列表Track Missing Package IDs in an Out-of-Order Receiving System
类型：online_judge
Out-of-Order Package Receiving System
Design a package receiving system. Every package has a non-negative integer ID starting from 0, but packages may arrive out of order.
The system must support two operations:
receivePackage(id): record that the package with ID id has been received.
getPackageStatus(): return:
the largest package ID received so far;
all package IDs that are still missing between 0 and that maximum ID, inclusive, in ascending order.
If no package has been received yet, a query should return -1 as the maximum ID and an empty missing list.
Receiving the same package ID more than once must not change the result.
Input Format
The first line contains an integer n, the number of operations.
Each of the next n lines is one of:
R id: call receivePackage(id);
Q: call getPackageStatus() and print the result.
Output Format
For every Q operation, print one line in this format:
max_id: missing_id_1 missing_id_2 ...
If there are no missing IDs, print nothing after the colon.
Constraints
1 <= n <= 100,000
0 <= id <= 100,000
Package IDs may arrive out of order and may be duplicated.
Example
Input:
8
R 2
Q
R 0
R 4
Q
R 1
R 3
Q
Output:
2: 0 1
4: 1 3
4:
Example
Input
8
R 2
Q
R 0
R 4
Q
R 1
R 3
Q
Output
2: 0 1
4: 1 3
4: