답안 #103696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103696 2019-04-02T04:53:06 Z 1234 Mecho (IOI09_mecho) C++14
2 / 100
468 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 sss) {
	H[x][y]=sss ;  
	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]=='D'){
				X2=i ; 
				Y2=j ; 
			}
			if(s[i][j]=='M'){
				X1=i ; 
				Y1=j ;
				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 ;
			q.pop() ; 
			good (x , y , cnt) ;
		} 
		cnt++ ;  
	}
	
	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 ; 
		}
	}
	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]
 }
 ^
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Runtime error 318 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 3 ms 384 KB Output isn't correct
12 Incorrect 2 ms 636 KB Output isn't correct
13 Runtime error 431 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Incorrect 215 ms 10524 KB Output isn't correct
15 Incorrect 3 ms 512 KB Output isn't correct
16 Incorrect 0 ms 384 KB Output isn't correct
17 Incorrect 2 ms 512 KB Output isn't correct
18 Incorrect 3 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 2 ms 512 KB Output isn't correct
23 Incorrect 2 ms 768 KB Output isn't correct
24 Incorrect 2 ms 640 KB Output isn't correct
25 Incorrect 2 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 3 ms 768 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 12 ms 2176 KB Output isn't correct
35 Runtime error 329 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Incorrect 11 ms 2432 KB Output isn't correct
37 Incorrect 12 ms 2432 KB Output isn't correct
38 Runtime error 303 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Incorrect 12 ms 2688 KB Output isn't correct
40 Incorrect 12 ms 2688 KB Output isn't correct
41 Runtime error 283 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 16 ms 3200 KB Output isn't correct
44 Runtime error 268 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Incorrect 16 ms 3448 KB Output isn't correct
46 Incorrect 17 ms 3452 KB Output isn't correct
47 Runtime error 273 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 25 ms 3704 KB Output isn't correct
49 Incorrect 22 ms 3712 KB Output isn't correct
50 Runtime error 304 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Incorrect 23 ms 4088 KB Output isn't correct
52 Incorrect 25 ms 4068 KB Output isn't correct
53 Runtime error 305 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Incorrect 33 ms 4344 KB Output isn't correct
55 Incorrect 38 ms 4344 KB Output isn't correct
56 Runtime error 330 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Incorrect 31 ms 4600 KB Output isn't correct
58 Incorrect 30 ms 4560 KB Output isn't correct
59 Runtime error 281 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Incorrect 33 ms 4856 KB Output isn't correct
61 Incorrect 29 ms 4856 KB Output isn't correct
62 Runtime error 256 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Correct 42 ms 4984 KB Output is correct
64 Incorrect 43 ms 4856 KB Output isn't correct
65 Incorrect 43 ms 4856 KB Output isn't correct
66 Incorrect 44 ms 4984 KB Output isn't correct
67 Incorrect 51 ms 4984 KB Output isn't correct
68 Correct 53 ms 4988 KB Output is correct
69 Incorrect 66 ms 4984 KB Output isn't correct
70 Incorrect 65 ms 4856 KB Output isn't correct
71 Incorrect 68 ms 4984 KB Output isn't correct
72 Incorrect 48 ms 4992 KB Output isn't correct
73 Runtime error 409 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 452 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 440 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 442 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 468 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 422 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 409 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 383 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 388 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 403 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 410 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 311 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 328 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 350 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 315 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 344 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 333 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 342 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 290 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 297 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)