#P9518. queue

    ID: 8798 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>模拟洛谷原创O2优化队列

queue

题目背景

你说的对,但是舞萌 DX 是一款后面忘了。

题目描述

补充说明:这里的排队和传统的排队有出入。正在游玩的人为队列的前两位,所以正在游玩视为正在排队。

机厅里有一台游戏机,每次可供最多两人同时游玩。但是来玩的人显然不止两个!这个时候他们就需要排队了,而你需要写一个程序维护这个队列,并在他人游玩结束后通知接下来上场的人。在整个过程中,有以下几种事件可能发生:

  • start:一局游戏开始。若这不是第一局游戏,则上一局的参与者在这一局游戏开始前一瞬间按照原本的顺序回到队尾。此时你应该按在队列中的顺序输出这一局上场的人的名字(正常来讲是队列前两位或者唯一一个人),若有两个则以空格分割。若这一局无人上场,则输出 Error 并忽略这条事件。

  • arrive xxx 到达机厅并且将自己加入队尾,此时 xx 不应该在排队,否则输出 Error 并忽略这条事件。若该事件成功执行则输出 OK

  • leave xxx 离开机厅并离开队列。此时 xx 应该在排队但不应该在游玩,否则输出 Error 并忽略这条事件。若该事件成功执行则输出 OK

你需要维护队列信息,并输出上述事件中要求的输出。

输入格式

第一行一个整数 nn,表示事件条数。

接下来 nn 行,每行表示一条事件。

输出格式

按照题目要求输出 nn 行,表示程序对事件的响应。

14
start
arrive A
start
arrive B
arrive C
arrive D
start
leave C
leave D
start
arrive A
arrive D
leave E
start
Error
OK
A
OK
OK
OK
B C
Error
OK
A B
Error
OK
Error
C D
3
arrive A
arrive B
arrive C
OK
OK
OK

提示

【样例说明】

样例 11 中发生了如下的事件:

  • 第一次 start 时队列并没有任何人,输出 Error
  • A 随即加入队列。
  • 第二次 start 时仅有 A 一个人,所以输出 A
  • B, C, D 随即依次加入队列。
  • 第三次 startB, C 上场。
  • C 试图离开,但是他在游玩。所以输出 Error
  • D 成功离开。
  • 第四次 startA, B 上场。
  • A 试图加入队列,但是他已经在队列中。输出 Error
  • D 重新加入队列。
  • E 试图离开,但是他根本不在排队,输出 Error
  • 第五次 startC, D 上场。

样例 22 中,A, B, C 依次入队,操作合法,输出三个 OK

【数据范围】

对于 20%20\% 的数据,保证 n=1n=1

对于 40%40\% 的数据,保证 n2000n\le 2000

对于另外 20%20\% 的数据,保证没有 leave 操作。

对于另外 20%20\% 的数据,人名只有可能是单个大写字母。

对于 100%100\% 的数据,保证 1n1051 \le n\le 10^5,人名仅含有大小写字母且长度不超过 1010

本题输入输出量较大,请注意使用合理的输入输出方式。