记录编号	92814	评测结果	AAAAAAAAAA
题目名称	[UVa 10881] 蚂蚁	最终得分	100
用户昵称	wolf	是否通过	通过
代码语言	C++	运行时间	0.127 s
提交时间	2014-03-22 21:45:38	内存使用	0.32 MiB

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
////////////////////
FILE *open;
FILE *out;
vector<int> id;
vector<int> ooldd;
vector<int> turn;
//
vector<int> newd;
vector<int> end;
///////////////////
int turnc(char c){
		if(c==76)
		return -1;//L
	else
		return 1;//R
}

int next_id(int a,int L){
	for(int i=a+1;i!=L+1;++i){
		if(id[i]>0)
			return i;//返回下一个id的位置
	}
	return 0;
}
int next_dir(int a,int L){
	for(int i=a;i!=L+1;++i){
		if(turn[i]>0){
			--turn[i];
			return i;//返回下一个方向所在位置
		}
	}
	return L+1;
}
int main(){
	open=fopen("Ants.in","r");
	out=fopen("Ants.out","w");
	int e,t=0;
	fscanf(open,"%d",&e);
	while(t!=e){
		fprintf(out,"Case #%d:\n",t+1);
		int L,T,n;
		fscanf(open,"%d%d%d",&L,&T,&n);
		id.resize(L+1,0);
		ooldd.resize(L+1,0);
		turn.resize(L+1,0);
		newd.resize(n+1,0);
		end.resize(n+1,0);
		int lfell,rfell;
		lfell=0;
		rfell=0;
		///////////
		for(int i=0;i!=n;++i){
			int a,b,end;
			char c;
			fscanf(open,"%d %c",&a,&c);
			id[a]=i+1;
			b=turnc(c);//direction
			end=a+b*T;
			if(end<0){
				++lfell;
			}
			else if(end>L){
				++rfell;
			}
			else{
				ooldd[end]+=b;
				++turn[end];
			}
		}
		//第一次哈希完成
		///////////
		int x,y,i;
		x=-1;
		y=0;
		i=0;
		///////////第二次哈希准备完成
		for(;;){
			if(lfell>0){
				x=next_id(x,L);//id[x] is end in end[]
				newd[id[x]]=-2;
				end[id[x]]=-1;
				++i;
				--lfell;
			}else
				break;
		}
		for(;i!=n;++i){
			y=next_dir(y,L);
			if(y<L+1){
				x=next_id(x,L);//id[x] is end in end[]
				newd[id[x]]=ooldd[y];
				end[id[x]]=y;
			}
		}
		for(;;){
			if(rfell>0){
				x=next_id(x,L);//id[x] is end in end[]
				newd[id[x]]=-2;
				end[id[x]]=-1;
				--rfell;
			}
			else
				break;
		}
		///////////第二次哈希完成
		for(int i=1;i!=n+1;++i){
			if(newd[i]==-2){
				fprintf(out,"Fell off\n");
			}
			else if(newd[i]==0){
				fprintf(out,"%d Turning\n",end[i]);
			}
			else if(newd[i]==-1){
				fprintf(out,"%d L\n",end[i]);
			}else
				fprintf(out,"%d R\n",end[i]);
		}
		///////////
		id.clear();
		ooldd.clear();
		turn.clear();
		newd.clear();
		end.clear();
		++t;
	}
	return 0;
}
//designed by wolf