立命館合宿2012 day3 問題D Dimensional Analysis (AOJ 2365)

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2365）

制約条件

m≦50000
各行は300字以下で、100行以下
mallocの引数は1以上

方針

構文解析+α
変数にはメモリ領域のIDをもたせておく。
メモリ領域は、IDごとに、サイズおよび解放済みフラグを持っておく。

メモリが割り当てられるたびに、領域に新たにIDを割り振るようにする。

問題文中にあるように、
malloc,cloneで領域が足りなかった場合には何もせずにNULLを返す、
free,cloneで、未定義または解放済みの領域を指定されたらErrorを出す、
free,cloneの引数がNULLだった場合は何もせずNULLを返す

ことに注意する。

最後に、使用メモリのうち、変数に割り当てられてない領域のサイズを求める。

ソースコード

int sz[100000],m;
bool released[100000];
map<string,int> v;
int mem,use;
string in;
bool err;

int rec(int l,int r){
	//cerr<<in.substr(l,r-l)<<endl;
	int i,d=0;
	for(i=l;i<r;i++){
		if(in[i]=='(')d++;
		if(in[i]==')')d--;
		if(d==0&&in[i]=='=')break;
	}
	if(i<r){
		return v[in.substr(l,i-l)]=rec(i+1,r);
	}
	d=0;
	for(i=r-1;i>=l;i--){
		if(in[i]==')')d++;
		if(in[i]=='(')d--;
		if(d==0)break;
	}
	if(i==r-1)return v[in.substr(l,r-l)];
	if(i==l)return rec(i+1,r-1);
	
	string op=in.substr(l,i-l);
	if(op=="malloc"){
		int s=atoi(in.substr(i+1,r-i-2).c_str());
		if(s<=mem-use){
			sz[m]=s;
			use+=s;
			return m++;
		}
		return -1;
	}
	if(op=="free"){
		int s=rec(i+1,r-1);
		if(s<0)return -1;
		if(s==0||released[s])err=1;
		else released[s]=1, use-=sz[s];
		return 0;
	}
	if(op=="clone"){
		int s=rec(i+1,r-1);
		if(s<0)return -1;
		if(s==0||released[s])return err=1, 0;
		if(sz[s]<=mem-use){
			sz[m]=sz[s];
			use+=sz[s];
			return m++;
		}
		return -1;
	}
	return v[in.substr(l,r-l)];
}
int main(){
	cin>>mem;
	m=1;
	v["NULL"]=-1;
	err=0;
	while(cin>>in){
		rec(0,in.size());
	}
	if(err)cout<<"Error"<<endl;
	else{
		fr(i,v)if(i->second>0&&!released[i->second]){
			released[i->second]=1;
			use-=sz[i->second];
		}
		cout<<use<<endl;
	}
	return 0;
	
}