oj.uz

답안 #138690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138690 2019-07-30T08:35:23 Z tinjyu Mecho (IOI09_mecho) C++14
16 / 100
 276 ms 34352 KB 
#include <iostream>
using namespace std;
int n,s;
char map[1005][1005],tmap[1005][1005];
int ex,ey,beetag[1005][1005],beartag[1005][1005],sx,sy,bee[1000005][3],bear[1000005][3];
int check(int step)
{
	
	//cout<<step<<endl;
	int beep=0,beepp=-1,bearp=0,bearpp=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			beetag[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;
				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*2,bearstep=0;
	while(count--)
	{
		bearstep+=s;
		while(bearp<=bearpp)
		{
			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)
				{
					bearpp++;
					bear[bearpp][0]=tmpx;
					bear[bearpp][1]=tmpy;
					bear[bearpp][2]=bear[bearp][2]+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++;
		}
	}
	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*2,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
16.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 396 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 6 ms 2680 KB Output is correct
7 Incorrect 187 ms 34248 KB Output isn't correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 10 ms 4984 KB Output is correct
10 Correct 7 ms 3260 KB Output is correct
11 Incorrect 60 ms 32760 KB Output isn't correct
12 Incorrect 3 ms 1016 KB Output isn't correct
13 Incorrect 76 ms 32760 KB Output isn't correct
14 Correct 78 ms 32760 KB Output is correct
15 Incorrect 2 ms 496 KB Output isn't correct
16 Incorrect 75 ms 32860 KB Output isn't correct
17 Incorrect 2 ms 632 KB Output isn't correct
18 Incorrect 74 ms 32760 KB Output isn't correct
19 Incorrect 2 ms 632 KB Output isn't correct
20 Incorrect 76 ms 32780 KB Output isn't correct
21 Incorrect 3 ms 760 KB Output isn't correct
22 Incorrect 76 ms 32716 KB Output isn't correct
23 Incorrect 3 ms 888 KB Output isn't correct
24 Incorrect 76 ms 32760 KB Output isn't correct
25 Incorrect 3 ms 888 KB Output isn't correct
26 Incorrect 76 ms 32756 KB Output isn't correct
27 Incorrect 3 ms 1020 KB Output isn't correct
28 Incorrect 79 ms 32808 KB Output isn't correct
29 Incorrect 4 ms 1020 KB Output isn't correct
30 Incorrect 79 ms 32820 KB Output isn't correct
31 Incorrect 3 ms 1016 KB Output isn't correct
32 Incorrect 76 ms 32760 KB Output isn't correct
33 Incorrect 21 ms 3832 KB Output isn't correct
34 Incorrect 92 ms 33144 KB Output isn't correct
35 Incorrect 94 ms 33212 KB Output isn't correct
36 Incorrect 26 ms 4472 KB Output isn't correct
37 Incorrect 97 ms 33272 KB Output isn't correct
38 Incorrect 99 ms 33304 KB Output isn't correct
39 Incorrect 31 ms 4980 KB Output isn't correct
40 Incorrect 102 ms 33272 KB Output isn't correct
41 Incorrect 105 ms 33292 KB Output isn't correct
42 Incorrect 38 ms 5496 KB Output isn't correct
43 Incorrect 108 ms 33400 KB Output isn't correct
44 Incorrect 112 ms 33400 KB Output isn't correct
45 Incorrect 46 ms 6136 KB Output isn't correct
46 Incorrect 116 ms 33692 KB Output isn't correct
47 Incorrect 121 ms 33576 KB Output isn't correct
48 Incorrect 53 ms 6648 KB Output isn't correct
49 Incorrect 122 ms 33628 KB Output isn't correct
50 Incorrect 129 ms 33656 KB Output isn't correct
51 Incorrect 63 ms 7164 KB Output isn't correct
52 Incorrect 131 ms 33784 KB Output isn't correct
53 Incorrect 139 ms 33768 KB Output isn't correct
54 Incorrect 71 ms 7672 KB Output isn't correct
55 Incorrect 142 ms 33828 KB Output isn't correct
56 Incorrect 154 ms 33952 KB Output isn't correct
57 Incorrect 81 ms 8316 KB Output isn't correct
58 Incorrect 154 ms 34144 KB Output isn't correct
59 Incorrect 161 ms 33912 KB Output isn't correct
60 Incorrect 97 ms 8936 KB Output isn't correct
61 Incorrect 159 ms 34140 KB Output isn't correct
62 Incorrect 177 ms 34156 KB Output isn't correct
63 Incorrect 161 ms 34040 KB Output isn't correct
64 Incorrect 163 ms 34140 KB Output isn't correct
65 Incorrect 159 ms 34048 KB Output isn't correct
66 Incorrect 160 ms 34040 KB Output isn't correct
67 Correct 160 ms 34160 KB Output is correct
68 Incorrect 197 ms 34060 KB Output isn't correct
69 Incorrect 207 ms 34040 KB Output isn't correct
70 Incorrect 198 ms 34040 KB Output isn't correct
71 Incorrect 198 ms 34216 KB Output isn't correct
72 Incorrect 186 ms 34156 KB Output isn't correct
73 Incorrect 276 ms 34268 KB Output isn't correct
74 Incorrect 185 ms 34092 KB Output isn't correct
75 Incorrect 185 ms 34168 KB Output isn't correct
76 Incorrect 184 ms 34040 KB Output isn't correct
77 Incorrect 184 ms 34040 KB Output isn't correct
78 Correct 187 ms 34152 KB Output is correct
79 Incorrect 189 ms 34192 KB Output isn't correct
80 Incorrect 201 ms 34140 KB Output isn't correct
81 Incorrect 222 ms 34168 KB Output isn't correct
82 Incorrect 189 ms 34164 KB Output isn't correct
83 Incorrect 187 ms 34168 KB Output isn't correct
84 Incorrect 187 ms 34104 KB Output isn't correct
85 Incorrect 217 ms 34352 KB Output isn't correct
86 Incorrect 186 ms 34264 KB Output isn't correct
87 Incorrect 184 ms 34168 KB Output isn't correct
88 Incorrect 185 ms 34040 KB Output isn't correct
89 Incorrect 194 ms 34112 KB Output isn't correct
90 Incorrect 184 ms 34168 KB Output isn't correct
91 Incorrect 184 ms 34152 KB Output isn't correct
92 Incorrect 183 ms 34088 KB Output isn't correct