제출 #138715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138715		tinjyu	Mecho (IOI09_mecho)	C++14	100 / 100	500 ms	17116 KiB

mecho

#include <iostream>
using namespace std;
int n,s;
char map[1005][1005],tmap[1005][1005],tag[1005][1005];
int ex,ey,beetag[1005][1005],beartag[1005][1005],sx,sy,bee[1000005][3],bear[1000005][3];
int check(int step)
{
	
	int beep=0,beepp=-1,bearp=0,bearpp=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			tag[i][j]=0;
			beartag[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(map[i][j]=='H')
			{
				beepp++;
				bee[beepp][0]=i;
				bee[beepp][1]=j;
				bee[beepp][2]=0;
			}
			if(map[i][j]=='M')
			{
				bear[0][0]=i;
				bear[0][1]=j;
				bear[0][2]=0;
				tag[i][j]=1;
				map[i][j]='G';
			}
		}
	}
	while(beep<=beepp)
	{
		if(bee[beep][2]==step)break;
		int nowx=bee[beep][0],nowy=bee[beep][1];
		for(int i=1;i<=4;i++)
		{
			int tmpx=nowx,tmpy=nowy;
			if(i==1)tmpx++;
			if(i==2)tmpy++;
			if(i==3)tmpx--;
			if(i==4)tmpy--;
			if((map[tmpx][tmpy]=='G' || map[tmpx][tmpy]=='M') && tmpx>0 && tmpy<=n && tmpy>0 && tmpy<=n)
			{
				beepp++;
				bee[beepp][0]=tmpx;
				bee[beepp][1]=tmpy;
				bee[beepp][2]=bee[beep][2]+1;
				map[tmpx][tmpy]='H';
			}
		}
		beep++;
	}
	for(int i=1;i<=n;i++)
	{
		//for(int j=1;j<=n;j++)cout<<map[i][j];
		//cout<<endl;
	}
	int count=n*n,bearstep=0;
	while(count--)
	{
		bearstep+=s;
		while(bearp<=bearpp)
		{
			//cout<<bear[bearp][0]<<" "<<bear[bearp][1]<<" "<<bear[bearp][2]<<endl;
			if(bear[bearp][2]==bearstep)break;
			int nowx=bear[bearp][0],nowy=bear[bearp][1];
			if(map[nowx][nowy]=='H')
			{
				bearp++;
				continue;
			}
			for(int i=1;i<=4;i++)
			{
				int tmpx=nowx,tmpy=nowy;
				if(i==1)tmpx++;
				if(i==2)tmpy++;
				if(i==3)tmpx--;
				if(i==4)tmpy--;
				if(map[tmpx][tmpy]=='D')return 1;
				if(map[tmpx][tmpy]=='G' && tmpx>0 && tmpy<=n && tmpy>0 && tmpy<=n && tag[tmpx][tmpy]==0)
				{
					bearpp++;
					bear[bearpp][0]=tmpx;
					bear[bearpp][1]=tmpy;
					bear[bearpp][2]=bear[bearp][2]+1;
					tag[tmpx][tmpy]=1;
				}
			}
			bearp++;
		}
		step++;
		//cout<<step<<" "<<count<<endl;
		while(beep<=beepp)
		{
			//cout<<bee[beep][0]<<" "<<bee[beep][1]<<" "<<bee[beep][2]<<endl;
			if(bee[beep][2]==step)break;
			int nowx=bee[beep][0],nowy=bee[beep][1];
			for(int i=1;i<=4;i++)
			{
				int tmpx=nowx,tmpy=nowy;
				if(i==1)tmpx++;
				if(i==2)tmpy++;
				if(i==3)tmpx--;
				if(i==4)tmpy--;
				if(map[tmpx][tmpy]=='G' && tmpx>0 && tmpy<=n && tmpy>0 && tmpy<=n)
				{
					beepp++;
					bee[beepp][0]=tmpx;
					bee[beepp][1]=tmpy;
					bee[beepp][2]=bee[beep][2]+1;
					map[tmpx][tmpy]='H';
				}
			}
			beep++;
		}
		//cout<<endl;
	}
	return 0;
}
int main()
{
	cin>>n>>s;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>map[i][j];
			tmap[i][j]=map[i][j];
		}
	}
	int l=0,r=n*n,ans=-1;
	while(l<=r)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				map[i][j]=tmap[i][j];
			}
		}
		int mid=(l+r)/2;
		if(check(mid)==1)
		{
			ans=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	cout<<ans;
}

• Subtask 1: 100 / 100