#P2167. 博物馆

    ID: 1556 传统题 文件IO:museum 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及− 上传者: 标签>数据结构栈基础算法模拟合肥市蜀山区区赛初中组IO 读写2026

博物馆

本题需要文件读写

文件 IO 为:输入文件 museum.in,输出文件 museum.out。请使用上述文件名读入和输出。

问题描述

博物馆新到一批文物,管理员依次执行以下指令:

  • PUSH x p:将编号为 xx、优先级为 pp 的文物放入待检区。p=2p=2 表示高优先级,p=1p=1 表示低优先级。
  • POP k:从待检区取出 kk 件文物进行检查。优先取高优先级文物,高优先级取完后再取低优先级文物;同一优先级内,先取最近放入的文物。如果待检区不足 kk 件,则全部取出,并记录一次“短缺”。

请输出所有被检查文物的编号,以及发生短缺的次数。

输入格式

从文件 museum.in 中读入数据。

第一行输入一个整数 qq,表示指令数量。

接下来 qq 行,每行输入一条指令,格式为 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

评测数据规模

对于所有数据,保证:

  • 1≤q≤1051\le q\le10^5;
  • 1≤x≤1091\le x\le10^9,p∈{1,2}p\in\{1,2\};
  • 1≤k≤1091\le k\le10^9。

每个测试点 1010 分,各测试点附加限制如下。

测试点 q≤q\le 特殊性质
1∼41\sim4 100100 所有 POP 指令的 k=1k=1
5∼75\sim7 50005000 无
8∼108\sim10 10510^5