#P2167. 博物馆
博物馆
本题需要文件读写
文件 IO 为:输入文件
museum.in,输出文件museum.out。请使用上述文件名读入和输出。
问题描述
博物馆新到一批文物,管理员依次执行以下指令:
PUSH x p:将编号为 、优先级为 的文物放入待检区。 表示高优先级, 表示低优先级。POP k:从待检区取出 件文物进行检查。优先取高优先级文物,高优先级取完后再取低优先级文物;同一优先级内,先取最近放入的文物。如果待检区不足 件,则全部取出,并记录一次“短缺”。
请输出所有被检查文物的编号,以及发生短缺的次数。
输入格式
从文件 museum.in 中读入数据。
第一行输入一个整数 ,表示指令数量。
接下来 行,每行输入一条指令,格式为 PUSH x p 或 POP k,含义如题目描述所示。
输出格式
输出到文件 museum.out 中。
第一行输出所有被检查文物的编号,按检查顺序排列,相邻编号之间用一个空格分隔。如果没有被检查的文物,第一行输出一个空行。
第二行输出一个整数,表示发生“短缺”的次数。
样例输入 1
6
PUSH 10 1
PUSH 20 2
POP 2
PUSH 30 1
PUSH 40 2
POP 3
样例输出 1
20 10 40 30
1
样例输入 2
4
POP 1
PUSH 5 1
POP 3
PUSH 6 2
样例输出 2
5
2
样例输入 3
6
PUSH 1 1
PUSH 2 1
PUSH 3 2
POP 1
POP 1
POP 1
样例输出 3
3 2 1
0
样例输入 4
5
PUSH 10 2
PUSH 20 1
PUSH 30 2
PUSH 40 1
POP 4
样例输出 4
30 10 40 20
0
样例输入 5
8
PUSH 1 1
PUSH 2 2
PUSH 3 1
PUSH 4 2
POP 10
POP 1
PUSH 5 1
POP 1
样例输出 5
4 2 3 1 5
2
评测数据规模
对于所有数据,保证:
- ;
- ,;
- 。
每个测试点 分,各测试点附加限制如下。
| 测试点 | 特殊性质 | |
|---|---|---|
所有 POP 指令的 |
||
| 无 | ||