IOI_official @ 2023-12-23 09:48:56
#include<bits/stdc++.h>
using namespace std;
int t,m,n,ii=1,jj,kk,ks,js,a[105],bb,ss,jjj=1,cc,iii;//这一大坨变量会在程序中解释
bool ff[114514],fff,ffff;//ff数组为调试用,ff[i]相当于h[i].f
struct node{
bool f;//此字节有没有被占
int b,s;//b是此字节所属内存块的编号,s是此内存块的字节数量
};
node h[100005];//内存条数组
string g;//操作
int main(){
scanf("%d%d",&t,&m);
for(int i=1;i<=t;i++){
cin>>g;
if(g!="defragment")
cin>>n;//如果操作不是defragment,就在后面再输入一个数字
if(g=="alloc"){
for(int j=1;j<=m;j++){
cc=0;//cc是内存条中连续空闲空间的长度
for(int k=j;k<=m;k++){
if(h[k].f==0){
cc++;
if(k==j){
ii=k;//ii是这段连续空闲空间的首地址
}
}
else break;//连续空闲空间中断就退出
}
if(cc>=n){
break;//如果这个连续空闲空间可以让要分配的内存长度插进去的话,就退出,将要分配的内存块插进此连续空闲空间中
}
}
if(cc<n){
cout<<"NULL"<<'\n';//如果内存条中没有够用的空间让要分配的内存块插就输出NULL
continue;//退出
}
if(ii+n-1>iii){
iii=ii+n;//iii是最后一个内存块的末尾地址+1
}
jj++;//jj是此内存块的编号
for(int j=ii;j<=ii+n-1;j++){
h[j].f=1;//将此字节标记为被占用
ff[j]=1;
h[j].b=jj;
}//从连续空闲空间的首地址一直循环n次
a[jj]=n;//此数组是用来存每个内存块的长度的
cout<<jj<<'\n';//输出编号
ss+=a[jj];//内存条中被占用的字节的数量
}
if(g=="erase"){
ffff=0;//标记
if(n<=0||n>jj){
cout<<"ILLEGAL_ERASE_ARGUMENT"<<'\n';
continue;
}//如果给的编号越界,就输出ILLEGAL_ERASE_ARGUMENT,然后退出
for(int j=1;j<=m;j++){
if(h[j].b==n){//如果找到了要删除的内存块
if(h[j].f==0){
cout<<"ILLEGAL_ERASE_ARGUMENT"<<'\n';
ffff=1;
break;
}//如果这个编号已经被删除过了,就输出ILLEGAL_ERASE_ARGUMENT,将标记变为1,退出
h[j].f=0;//如果没被删除过,就将它删除
ff[j]=0;
}
}
if(ffff==1)continue;//如果有标记,跳出
ss-=a[n];
if(n==jj){
iii=ss-a[n]+1;//总数-最靠近内存条末尾内存块的长度+1
}//如果删的是最靠近内存条末尾的内存块,就更改最ii的值(最后一个内存块的末尾地址+1)
a[n]=0;//将此内存块的长度变为0
}
if(g=="defragment"){
for(int k=1;k<=m;k++){
for(int j=1;j<=m;j++){
if(h[j].f==0&&ks==0&&iii>j){
ks=j;//ks为向左移最多能移到哪
continue;
}//如果此字节未被占用,且ks没值,且当前字节在最靠末尾的被占用的字节的前面
if(h[j].f==1&&ks!=0){
js=j;//js是要被移动的内存块的左端点的位置
bb=h[j].b;//bb是要被移动的内存块的长度
break;//找到后退出
}
}
if(ks!=0&&js!=0){//如果ks和js都不为空
for(int j=js;j<=a[bb]+js-1;j++){//循环从js开始,循环要移动的内存块的长度次
h[j].f=0;//将此字节变为0
ff[j]=0;
h[ks+j-js].f=1;//ks+j-js是这个字节要移动到的地址
ff[ks+j-js]=1;
}
iii=ss+1;//整理完后ii会变成总数+1
}
ks=0;//ks归0
}
}
}
return 0;
}