English · Original
Chinese · Translation
Formal · Original
There is little time left before the release of the first national operating system BerlOS. Some of its components are not finished yet — the memory manager is among them. According to the developers' plan, in the first release the memory manager will be very simple and rectilinear. It will support three operations:
* _alloc n_ — to allocate _n_ bytes of the memory and return the allocated block's identifier _x_;
* _erase x_ — to erase the block with the identifier _x_;
* _defragment_ — to defragment the free memory, bringing all the blocks as close to the beginning of the memory as possible and preserving their respective order;
The memory model in this case is very simple. It is a sequence of _m_ bytes, numbered for convenience from the first to the _m_\-th.
The first operation _alloc n_ takes as the only parameter the size of the memory block that is to be allocated. While processing this operation, a free block of _n_ successive bytes is being allocated in the memory. If the amount of such blocks is more than one, the block closest to the beginning of the memory (i.e. to the first byte) is prefered. All these bytes are marked as not free, and the memory manager returns a 32-bit integer numerical token that is the identifier of this block. If it is impossible to allocate a free block of this size, the function returns _NULL_.
The second operation _erase x_ takes as its parameter the identifier of some block. This operation frees the system memory, marking the bytes of this block as free for further use. In the case when this identifier does not point to the previously allocated block, which has not been erased yet, the function returns _ILLEGAL_ERASE_ARGUMENT_.
The last operation _defragment_ does not have any arguments and simply brings the occupied memory sections closer to the beginning of the memory without changing their respective order.
In the current implementation you are to use successive integers, starting with 1, as identifiers. Each successful _alloc_ operation procession should return following number. Unsuccessful _alloc_ operations do not affect numeration.
You are to write the implementation of the memory manager. You should output the returned value for each _alloc_ command. You should also output _ILLEGAL_ERASE_ARGUMENT_ for all the failed _erase_ commands.
## Input
The first line of the input data contains two positive integers _t_ and _m_ (1 ≤ _t_ ≤ 100;1 ≤ _m_ ≤ 100), where _t_ — the amount of operations given to the memory manager for processing, and _m_ — the available memory size in bytes. Then there follow _t_ lines where the operations themselves are given. The first operation is _alloc n_ (1 ≤ _n_ ≤ 100), where _n_ is an integer. The second one is _erase x_, where _x_ is an arbitrary 32-bit integer numerical token. The third operation is _defragment_.
## Output
Output the sequence of lines. Each line should contain either the result of _alloc_ operation procession , or _ILLEGAL_ERASE_ARGUMENT_ as a result of failed _erase_ operation procession. Output lines should go in the same order in which the operations are processed. Successful procession of _alloc_ operation should return integers, starting with 1, as the identifiers of the allocated blocks.
[samples]
在首个国产操作系统 BerlOS 发布前，时间所剩无几，部分组件尚未完成——内存管理器便是其中之一。根据开发计划，首个版本的内存管理器将非常简单且线性。它将支持三种操作：
此时的内存模型非常简单：它是一个包含 #cf_span[m] 字节的序列，为方便起见，从第 1 字节编号至第 #cf_span[m] 字节。
第一个操作 _alloc n_ 仅接受一个参数，即要分配的内存块大小。处理该操作时，将在内存中分配一个大小为 #cf_span[n] 的连续空闲字节块。若有多个这样的块，则优先选择最靠近内存起始端（即第 1 字节）的块。这些字节将被标记为非空闲，内存管理器返回一个 32 位整数标识符作为该块的编号。若无法分配如此大小的空闲块，则函数返回 _NULL_。
第二个操作 _erase x_ 接受一个标识符作为参数。该操作释放系统内存，将该块的字节标记为空闲以供后续使用。若该标识符未指向先前已分配且尚未被释放的块，则函数返回 _ILLEGAL_ERASE_ARGUMENT_。
最后一个操作 _defragment_ 不接受任何参数，仅将已占用的内存段向内存起始端移动，同时保持各段的相对顺序不变。
在当前实现中，应使用从 1 开始的连续整数作为标识符。每次成功的 _alloc_ 操作应返回下一个编号。失败的 _alloc_ 操作不影响编号序列。
你需要实现内存管理器。对于每个 _alloc_ 命令，输出其返回值；对于所有失败的 _erase_ 命令，输出 _ILLEGAL_ERASE_ARGUMENT_。
输入的第一行包含两个正整数 #cf_span[t] 和 #cf_span[m]（#cf_span[1 ≤ t ≤ 100;1 ≤ m ≤ 100]），其中 #cf_span[t] 表示提供给内存管理器处理的操作数量，#cf_span[m] 表示可用内存的字节数。随后有 #cf_span[t] 行，每行给出一个操作：第一种是 _alloc n_（#cf_span[1 ≤ n ≤ 100]），其中 #cf_span[n] 是一个整数；第二种是 _erase x_，其中 #cf_span[x] 是任意 32 位整数标识符；第三种是 _defragment_。
输出一系列行。每行应包含 _alloc_ 操作的执行结果，或失败的 _erase_ 操作返回的 _ILLEGAL_ERASE_ARGUMENT_。输出行的顺序应与操作处理顺序一致。成功的 _alloc_ 操作应返回从 1 开始的整数作为分配块的标识符。
## Input
The first line of the input data contains two positive integers #cf_span[t] and #cf_span[m] (#cf_span[1 ≤ t ≤ 100;1 ≤ m ≤ 100]), where #cf_span[t] — the amount of operations given to the memory manager for processing, and #cf_span[m] — the available memory size in bytes. Then there follow #cf_span[t] lines where the operations themselves are given. The first operation is _alloc n_ (#cf_span[1 ≤ n ≤ 100]), where #cf_span[n] is an integer. The second one is _erase x_, where #cf_span[x] is an arbitrary 32-bit integer numerical token. The third operation is _defragment_.
## Output
Output the sequence of lines. Each line should contain either the result of _alloc_ operation procession , or _ILLEGAL_ERASE_ARGUMENT_ as a result of failed _erase_ operation procession. Output lines should go in the same order in which the operations are processed. Successful procession of _alloc_ operation should return integers, starting with 1, as the identifiers of the allocated blocks.
[samples]
**Definitions**
Let $ t \in \mathbb{Z}^+ $ be the number of operations.
Let $ m \in \mathbb{Z}^+ $ be the total memory size (in bytes), indexed from $ 1 $ to $ m $.
Let $ M = (M_1, M_2, \dots, M_m) $ be a memory state vector, where $ M_i \in \mathbb{Z}_{\geq 0} $ denotes the block identifier occupying byte $ i $, or $ 0 $ if free.
Let $ \text{id}_\text{next} \in \mathbb{Z}^+ $ be the next available block identifier, initially $ 1 $.
Let $ \text{allocated} \subseteq \mathbb{Z}^+ $ be the set of currently allocated (not erased) block identifiers.
**Constraints**
1. $ 1 \leq t \leq 100 $
2. $ 1 \leq m \leq 100 $
3. For each operation:
- If `alloc n`: $ 1 \leq n \leq 100 $
- If `erase x`: $ x \in \mathbb{Z} $, arbitrary 32-bit integer
- If `defragment`: no arguments
**Operations**
For each operation in sequence:
1. **`alloc n`**:
Find the leftmost contiguous segment of $ n $ free bytes:
$$
\min \left\{ j \in \{1, \dots, m - n + 1\} \ \middle|\ \forall i \in [j, j+n-1],\ M_i = 0 \right\}
$$
If such $ j $ exists:
- Set $ M_i \leftarrow \text{id}_\text{next} $ for all $ i \in [j, j+n-1] $
- Add $ \text{id}_\text{next} $ to $ \text{allocated} $
- Output $ \text{id}_\text{next} $
- Increment $ \text{id}_\text{next} \leftarrow \text{id}_\text{next} + 1 $
Else:
- Output `NULL` (but per problem, only output on success; failure implies no output? — **Note**: Problem says “output the returned value”, and `NULL` is returned, but output instructions say to output only for successful `alloc` and failed `erase`. So `NULL` is not printed.)
→ **Clarification from problem**: Only output the identifier on successful `alloc`; no output for `NULL`.
2. **`erase x`**:
If $ x \notin \text{allocated} $:
- Output `ILLEGAL_ERASE_ARGUMENT`
Else:
- Set $ M_i \leftarrow 0 $ for all $ i $ such that $ M_i = x $
- Remove $ x $ from $ \text{allocated} $
3. **`defragment`**:
Rearrange memory so that all allocated blocks are moved contiguously to the beginning, preserving their relative order.
Let $ B_1, B_2, \dots, B_k $ be the list of allocated blocks in order of their original leftmost byte position.
For each block $ b \in \{B_1, \dots, B_k\} $:
- Let $ s_b $ be its size (number of bytes with identifier $ b $)
- Place block $ b $ starting at the next available position (after previous blocks), without gaps.
- Update $ M $ accordingly.
(Block identifiers remain unchanged; only positions change.)
**Objective**
For each operation, output:
- The block identifier (starting from 1, incremented per successful `alloc`) on successful `alloc`
- `ILLEGAL_ERASE_ARGUMENT` on failed `erase`
- Nothing for `defragment` or failed `alloc` (i.e., `NULL`)
**Note**: `NULL` is not printed; only successful `alloc` and failed `erase` produce output.
API Response (JSON)
{
"problem": {
"name": "B. Memory Manager",
"description": {
"content": "There is little time left before the release of the first national operating system BerlOS. Some of its components are not finished yet — the memory manager is among them. According to the developers'",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 65536
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF7B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There is little time left before the release of the first national operating system BerlOS. Some of its components are not finished yet — the memory manager is among them. According to the developers'...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在首个国产操作系统 BerlOS 发布前，时间所剩无几，部分组件尚未完成——内存管理器便是其中之一。根据开发计划，首个版本的内存管理器将非常简单且线性。它将支持三种操作：\n\n此时的内存模型非常简单：它是一个包含 #cf_span[m] 字节的序列，为方便起见，从第 1 字节编号至第 #cf_span[m] 字节。\n\n第一个操作 _alloc n_ 仅接受一个参数，即要分配的内存块大小。处理该操作时...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ t \\in \\mathbb{Z}^+ $ be the number of operations. \nLet $ m \\in \\mathbb{Z}^+ $ be the total memory size (in bytes), indexed from $ 1 $ to $ m $. \nLet $ M = (M_1, M_2, \\dots, M...",
"is_translate": false,
"language": "Formal"
}
]
}