Submission #103695

# Submission time Handle Problem Language Result Execution time Memory
103695 2019-04-02T04:48:28 Z 1234 Mecho (IOI09_mecho) C++14
2 / 100
328 ms 66560 KB
#include <bits/stdc++.h>
using namespace std ;

bool b[805][805] , bm[805][805];  
string s[805] ; 
int fuck , X1 , Y1 , X2 , Y2 , n , ss , a[805][805] , H[805][805];
queue <pair <int , int > > q , qm; 

void good(int x , int y , int low) {
	H[x][y]=low ;  
	b[x][y]=1 ;
//	if(y-1>=0 && b[x][y-1]==0) q.push(make_pair(x , y-1)) ;  
//	if(y+1 < n && b[x][y+1]==0) q.push(make_pair(x , y+1)) ;  
//	if(x-1>=0 && b[x-1][y]==0) q.push(make_pair(x-1 , y)) ;  
//	if(x+1 < n && b[x+1][y]==0) q.push(make_pair(x+1 , y)) ;  
}

bool pro(int mid) {
	int ll=0 ; 
	while (qm.empty()==0) {
		int siz=qm.size(); 
		int cnt=0 ; 
		while (siz--) {
			cnt++ ; 
			int x=qm.front().first ;  	
			int y=qm.front().second ;  	
			qm.pop() ;
			if(x==X2 && y==Y2) {
				fuck = cnt ; 
				break ; 
			} 
			bm[x][y] = 1 ; 
			if(y-1>=0 && bm[x][y-1]==0 &&  H[x][y-1] < (cnt/ss)+mid) qm.push(make_pair(x , y-1)) ;  
			if(y+1 < n && bm[x][y+1]==0 &&  H[x][y+1] < (cnt/ss)+mid) qm.push(make_pair(x , y+1)) ;  
			if(x-1>=0 && bm[x-1][y]==0 &&  H[x-1][y] < (cnt/ss)+mid) qm.push(make_pair(x-1 , y)) ;  
			if(x+1 < n && bm[x+1][y]==0 &&  H[x+1][y] < (cnt/ss)+mid) qm.push(make_pair(x+1 , y)) ;
		}
		if(fuck%ss==0 && fuck!=-1) {
			if(cnt/ss+mid > H[X2][Y2]) return 1 ;
			else return 0 ;  	
		}
		if(fuck%ss!=0 && fuck!=-1) {
			if(fuck/ss+1+mid > H[X2][Y2]) return 1 ;
			else return 0 ;  				
		}
	}
}

int main(){
	fuck = -1 ; 
	cin >> n >> ss ; 
	for(int i=0 ; i<n ; i++){
		cin >> s[i] ; 			
		for(int j=0 ; j<n ; j++){
			if(s[i][j]=='T') {
				b[i][j]=1 ; 
				bm[i][j]=1 ; 
			}
			if(s[i][j]=='H') {
				q.push(make_pair(i , j)) ; 
				b[i][j]=1 ; 
				bm[i][j] = 1 ; 
			}
			if(s[i][j]=='M'){
				X2=i ; 
				Y2=j ; 
			}
			if(s[i][j]=='D'){
				X1=i ; 
				Y1=j ;
				b[i][j]=1; 
				qm.push(make_pair(X1 , Y1)) ; 
			}
		}
	}	
	int cnt = 0 ; 
	while (q.empty()==0) {
		int siz=q.size() ;
		while (siz--){
			int x=q.front().first ; 
			int y=q.front().second ;
			b[x][y]=1 ;
			q.pop() ; 
		
			if(y-1>=0 && b[x][y-1]==0) {
				q.push(make_pair(x , y-1)) ; 
				b[x][y-1]=1 ; 	
			}  
			if(y+1 < n && b[x][y+1]==0) {
				q.push(make_pair(x , y+1)) ;
				b[x][y+1] = 1 ; 
			} 
			if(x-1>=0 && b[x-1][y]==0) {
				q.push(make_pair(x-1 , y)) ; 
				b[x-1][y] = 1 ; 
			}  
			if(x+1 < n && b[x+1][y]==0) {
				q.push(make_pair(x+1 , y)) ;
				b[x+1][y]=1 ; 
			} 
	
	
			good (x , y , cnt) ;
		} 
		cnt++ ;  
	}
//	
//	for(int i=0 ; i<n ;i++){
//		for(int j=0 ; j<n ; j++){
//			printf("%3d",H[i][j]) ;  
//		}
//		cout << endl ; 
//	}
//	
	int m1=0 , m2=H[X2][Y2] ;  
	while (m1 != m2) {
		int mid=(m1+m2+1)/2 ; 
		if(1 == pro(mid) ) {
			m1=mid ; 
		}	
		else {
			m2=mid-1 ; 
		}
	}
	if(m2==0) {
		cout << -1 << endl ; 
		return 0 ; 
	}
	else {
		cout << m2 << endl ;
	}
}

Compilation message

mecho.cpp: In function 'bool pro(int)':
mecho.cpp:19:6: warning: unused variable 'll' [-Wunused-variable]
  int ll=0 ; 
      ^~
mecho.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 3 ms 384 KB Output isn't correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Runtime error 292 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Incorrect 2 ms 384 KB Output isn't correct
9 Incorrect 2 ms 384 KB Output isn't correct
10 Incorrect 2 ms 384 KB Output isn't correct
11 Incorrect 2 ms 384 KB Output isn't correct
12 Incorrect 3 ms 640 KB Output isn't correct
13 Incorrect 2 ms 640 KB Output isn't correct
14 Runtime error 328 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Incorrect 3 ms 512 KB Output isn't correct
16 Incorrect 3 ms 512 KB Output isn't correct
17 Incorrect 3 ms 512 KB Output isn't correct
18 Incorrect 2 ms 512 KB Output isn't correct
19 Incorrect 2 ms 512 KB Output isn't correct
20 Incorrect 3 ms 512 KB Output isn't correct
21 Incorrect 3 ms 512 KB Output isn't correct
22 Incorrect 3 ms 512 KB Output isn't correct
23 Incorrect 3 ms 640 KB Output isn't correct
24 Incorrect 3 ms 640 KB Output isn't correct
25 Incorrect 3 ms 640 KB Output isn't correct
26 Incorrect 2 ms 640 KB Output isn't correct
27 Incorrect 3 ms 640 KB Output isn't correct
28 Incorrect 3 ms 640 KB Output isn't correct
29 Incorrect 2 ms 640 KB Output isn't correct
30 Incorrect 4 ms 768 KB Output isn't correct
31 Incorrect 3 ms 768 KB Output isn't correct
32 Incorrect 3 ms 768 KB Output isn't correct
33 Incorrect 9 ms 2176 KB Output isn't correct
34 Incorrect 9 ms 2176 KB Output isn't correct
35 Runtime error 246 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Incorrect 10 ms 2432 KB Output isn't correct
37 Incorrect 11 ms 2432 KB Output isn't correct
38 Runtime error 327 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Incorrect 13 ms 2688 KB Output isn't correct
40 Incorrect 18 ms 2712 KB Output isn't correct
41 Runtime error 305 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Incorrect 19 ms 3200 KB Output isn't correct
43 Incorrect 15 ms 3200 KB Output isn't correct
44 Runtime error 300 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Incorrect 17 ms 3456 KB Output isn't correct
46 Incorrect 17 ms 3456 KB Output isn't correct
47 Runtime error 296 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 21 ms 3836 KB Output isn't correct
49 Incorrect 19 ms 3792 KB Output isn't correct
50 Runtime error 278 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Incorrect 28 ms 3964 KB Output isn't correct
52 Incorrect 25 ms 4096 KB Output isn't correct
53 Runtime error 296 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Incorrect 27 ms 4344 KB Output isn't correct
55 Incorrect 28 ms 4344 KB Output isn't correct
56 Runtime error 298 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Incorrect 28 ms 4608 KB Output isn't correct
58 Incorrect 33 ms 4600 KB Output isn't correct
59 Runtime error 300 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Incorrect 34 ms 4984 KB Output isn't correct
61 Incorrect 45 ms 4856 KB Output isn't correct
62 Runtime error 303 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Incorrect 49 ms 4984 KB Output isn't correct
64 Incorrect 54 ms 4984 KB Output isn't correct
65 Incorrect 41 ms 4856 KB Output isn't correct
66 Incorrect 45 ms 4856 KB Output isn't correct
67 Correct 42 ms 4880 KB Output is correct
68 Incorrect 57 ms 4984 KB Output isn't correct
69 Incorrect 45 ms 4864 KB Output isn't correct
70 Incorrect 44 ms 4956 KB Output isn't correct
71 Incorrect 47 ms 5056 KB Output isn't correct
72 Incorrect 47 ms 4864 KB Output isn't correct
73 Incorrect 42 ms 5240 KB Output isn't correct
74 Incorrect 43 ms 5240 KB Output isn't correct
75 Incorrect 43 ms 5248 KB Output isn't correct
76 Incorrect 42 ms 5248 KB Output isn't correct
77 Incorrect 40 ms 5112 KB Output isn't correct
78 Runtime error 272 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 280 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 280 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 311 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 267 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 285 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 294 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Incorrect 59 ms 5112 KB Output isn't correct
86 Runtime error 273 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 280 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 317 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 298 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 282 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 284 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 275 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)