← 返回题目列表

Codeforces · 7/B

B. 内存管理器

中文机器翻译题面 查看原题

距离第一个国产操作系统 BerlOS 发布已经所剩无几了。它的一些组件尚未完成——内存管理器就是其中之一。根据开发人员的计划,在第一个版本中,内存管理器将非常简单且直线。它将支持三种操作:

- alloc n — 分配 n 个字节的内存并返回分配块的标识符 x;
- 擦除 x — 擦除标识符为 x 的块;
- 碎片整理 — 对可用内存进行碎片整理,使所有块尽可能靠近内存的开头并保留它们各自的顺序;

这种情况下的内存模型非常简单。它是一个 m 字节的序列,为方便起见,从第一个字节到第 m 个字节进行编号。

第一个操作 alloc n 将要分配的内存块的大小作为唯一参数。在处理此操作时,将在内存中分配一个由 n 个连续字节组成的空闲块。如果此类块的数量超过一个,则优先选择最接近内存开头(即第一个字节)的块。所有这些字节都被标记为不空闲,并且内存管理器返回一个 32 位整数数字标记,它是该块的标识符。如果无法分配该大小的空闲块,则该函数返回 NULL。

第二个操作erase x 将某个块的标识符作为其参数。此操作释放系统内存,将该块的字节标记为可供进一步使用。如果该标识符不指向先前分配的块(该块尚未被擦除),则该函数返回 ILLEGAL_ERASE_ARGUMENT。

最后一个操作碎片整理没有任何参数,只是使占用的内存部分更接近内存的开头,而不改变它们各自的顺序。

在当前实现中,您将使用从 1 开始的连续整数作为标识符。每个成功的分配操作进程应返回以下数字。不成功的分配操作不会影响计数。

你要编写内存管理器的实现。您应该输出每个分配命令的返回值。您还应该为所有失败的擦除命令输出 ILLEGAL_ERASE_ARGUMENT。

输入

输入数据的第一行包含两个正整数 t 和 m (1 ≤ t ≤ 100;1 ≤ m ≤ 100),其中 t — 给予内存管理器处理的操作量,m — 可用内存大小(以字节为单位)。接下来的 t 行给出了操作本身。第一个操作是 alloc n (1 ≤ n ≤ 100),其中 n 是整数。第二个是擦除 x,其中 x 是任意 32 位整数数字标记。第三个操作是碎片整理。

输出

输出行序列。每行应包含 alloc 操作 procession 的结果,或作为擦除操作 procession 失败的结果的 ILLEGAL_ERASE_ARGUMENT。输出行的顺序应与处理操作的顺序相同。成功执行alloc操作应返回从1开始的整数,作为分配块的标识符。

示例

输入 #1

6 10
alloc 5
alloc 3
erase 1
alloc 6
defragment
alloc 6

输出 #1

1
2
NULL
3