首页 > 试题广场 >

任务调度

[编程题]任务调度
任务调度是计算机系统中一项重要的工作。
今天你的任务,就是模拟一个计算机系统模型的任务调度过程,并给出相应操作的执行结果。
在这个模型中,不同任务按照一定顺序到来,等待被执行。
任务处理机制需要维护任务的等待情况,并在相应的时机选择相应的任务进行执行。
不同的任务之间以编号进行区分,为方便起见,按照任务到来的顺序,由先到后编号为 1, 2, 3...。
每个任务都拥有一个重要程度 a_i,所有任务的重要程度两两不同。
在一般情况下,处理任务应当按照任务到来的先后顺序依次处理,也就是说任务等待应当形成一个队列。
但考虑到不同任务的重要程度不同,这一原则可能被打破。
具体而言,有如下几种操作:
1. 1 a_i:一个新的任务到来,其编号为先前出现过的最大任务编号 +1,其重要程度为 a_i,在任务等待队列中被安排至队列末尾。
考虑到计算机内存限制,同一时刻正在等待的任务数量不能超过 m,因此如果当前已经有 m 个任务在等待,则这一操作将出现错误。
2. 2 a_i x_i:一个新的任务到来,其编号为先前出现过的最大任务编号 +1,其重要程度为 a_i,在任务等待队列中被安排至任务编号为 x_i 的任务前面并紧挨任务 x_i 的位置。
如果当前已有 m 个任务在等待,或任务 x_i 当前不在等待队列中,这一操作将出现错误。
3. 3:任务处理机制将处理当前排在等待队列队首的任务,并将其从等待队列中移除。
若当前等待队列为空,这一操作将出现错误。
4. 4:任务处理机制将处理当前等待队列中重要程度最大的任务,并将其从等待队列中移除。
若当前等待队列为空,这一操作将出现错误。
除上述提到的错误情况外,操作均可以成功执行。
最开始,任务等待队列为空,接下来你需要处理 n 个操作,每个操作形如上述几种之一。
对于每个操作,你需要正确判断是否会出现错误,如果出现错误,需要输出一个 ERR,并不予以执行(但对于操作 12 而言,仍会占用一个新的任务编号);如果可以成功执行,则需要输出一个正整数,表示这次操作涉及到的任务编号,在操作 12 中表示新到来的任务编号,操作 34 中表示被处理的任务编号。

输入描述:
从标准输入读入数据。
输入的第一行包含两个正整数 n, m,分别表示需要执行的操作个数和队伍的最大容量。
接下来 n 行,每行按上述格式描述一个操作。
对于全部的数据,保证:1 \leq n, m \leq 5 \times 10^51 \leq a_i, x_i \leq n,所有 a_i 两两不同。


输出描述:
输出到标准输出。
输出 n 行,每行表示对应操作执行的结果,格式如上所述。
示例1

输入

12 3
1 2
1 6
2 1 2
2 7 3
1 5
3
3
1 8
2 4 3
4
4
4

输出

1
2
3
ERR
ERR
1
3
6
ERR
6
2
ERR

这道题你会答吗?花几分钟告诉大家答案吧!