답안 #777246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777246	2023-07-08T20:20:48 Z	_ZeyadRafat	Mecho (IOI09_mecho)	C++14	100 / 100	501 ms	6348 KB

mecho

#include <bits/stdc++.h>
using namespace std;

long long  gcd(long long a, long long b){
    if(b == 0) return a;
    return gcd(b, a % b);
}
long long _gcd(long long n1,long long n2)
{  while (n2!=0){
        long long temp=n1;
        n1=n2;
        n2=temp%n1;
    }
    return n1;
}
long long _lcm(long long n1,long long n2){
    return (n1/ _gcd(n1,n2))*n2;
}

bool prime(long long n){
    if(n==2)return true;
    if(n<2||n%2==0)return false;
    int d= sqrtl(n);
    for(int i=3;i<= d;i+=2)
        if(n%i==0)return false;
    return true;
}

string to_binary(long long x){
    string s="";
    while(x){
        int d=x%2;
        char c=d+'0';
        s+=c;
        x/=2;
    }
    return s;
}
long long to_dec(string s){
    long long su=0;


    int d=0;

    for(long long  i=0;i<(s.size());i++){
        if(s[i]=='0')continue;
        long long q= round(pow(2LL,i));
        su+=q;
    }
    return su;
}
bool com(pair<long long ,long long >&x,pair<long long ,long long >&y){
	if(x.first!=y.first)return x.first>y.first;
	return x.second<y.second;
}
void Nozarashi(){
	long long n,k;
	cin>>n>>k;
	vector<string>grid;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		grid.push_back(s);
	}
	long long s1,s2;
	for(int i=0;i<int(grid.size());i++){
		for(int j=0;j<int(grid[i].size());j++){
			if(grid[i][j]=='M'){
             s1=i;
             s2=j;
			}

		}
	}
	function<bool(int ,int,int,int)>in_range=[&](int i,int j,int n,int m){
		if(i>=0&&i<n&&j>=0&&j<m)return true;
		return false;
	};
   function<bool(long long ) >bfs=[&](long long mi){
   long long visted[n+3][n+3];
   memset(visted,0,sizeof(visted));
   queue<pair<int,int> >qe;
   for(int i=0;i<n;i++){
   	for(int j=0;j<n;j++){
   		if(grid[i][j]=='H'){qe.push({i,j});
   		   		visted[i][j]=true;}
   	}
   }
   int level=0;
   while(!qe.empty()){
   	if(level==mi)break;
   	long long sz=qe.size();
   	for(int d=0;d<sz;d++){
   		long long i=qe.front().first;
   		long long j=qe.front().second;

   		qe.pop();
   		for(int I=-1;I<=1;I++){
   			for(int J=-1;J<=1;J++){
   				if(abs(I)==abs(J))continue;
   				long long t1=i+I;
   				long long t2=j+J;
   				if(!in_range(t1,t2,n,n))continue;
   				if(visted[t1][t2])continue;
   				if(grid[t1][t2]=='M'){
   					return false;
   				}
   				if(grid[t1][t2]=='D')continue;
   				if(grid[t1][t2]=='T')continue;
   				qe.push({t1,t2});
   				visted[t1][t2]=true;
   			}
   		}
   	}
   	level++;
   }
   level=0;
   queue<pair<int,int > >qem;
   qem.push({s1,s2});
   visted[s1][s2]=true;

   while(!qem.empty()||!qe.empty()){

   	long long sz=qe.size();
   	if((level+1)%k==0){
   	for(int d=0;d<sz;d++){
   		long long i=qe.front().first;
   		long long j=qe.front().second;
   		qe.pop();

   		for(int I=-1;I<=1;I++){
   			for(int J=-1;J<=1;J++){
   				if(abs(I)==abs(J))continue;
   				long long t1=i+I;
   				long long t2=j+J;
   				if(!in_range(t1,t2,n,n))continue;
   				if(visted[t1][t2])continue;

   				if(grid[t1][t2]=='T')continue;

   				if(grid[t1][t2]=='D')continue;

   				qe.push({t1,t2});
   				visted[t1][t2]=true;

   		}
   	}
   	}
   	sz=qem.size();
   		for(int d=0;d<sz;d++){
   		long long i=qem.front().first;
   		long long j=qem.front().second;
   		qem.pop();

   		for(int I=-1;I<=1;I++){
   			for(int J=-1;J<=1;J++){
   				if(abs(I)==abs(J))continue;
   				long long t1=i+I;
   				long long t2=j+J;
   				if(!in_range(t1,t2,n,n))continue;
   				if(visted[t1][t2])continue;

   				if(grid[t1][t2]=='D')return true;

   				if(grid[t1][t2]=='T')continue;
   				if(grid[t1][t2]=='D')return true;
   				qem.push({t1,t2});
   				visted[t1][t2]=true;

   		}
   	}
   	}
   	}
  else {
     sz=qem.size();
   		for(int d=0;d<sz;d++){
   		long long i=qem.front().first;
   		long long j=qem.front().second;
   		qem.pop();

   		for(int I=-1;I<=1;I++){
   			for(int J=-1;J<=1;J++){
   				if(abs(I)==abs(J))continue;
   				long long t1=i+I;
   				long long t2=j+J;
   				if(!in_range(t1,t2,n,n))continue;
   				if(visted[t1][t2])continue;
   				if(grid[t1][t2]=='T')continue;
   				if(grid[t1][t2]=='D')return true;

   				qem.push({t1,t2});
   				visted[t1][t2]=true;

   		}
   	}
   	}
  }
  level++;
   }
  return false;
   };
long long l=0,r=1e6,ans=-1;
while(l<=r){
	long long mid=l+(r-l)/2;

	if(bfs(mid)){
		l=mid+1;
		ans=mid;
	}
	else r=mid-1;
}
cout<<ans<<endl;
}


int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);


    //// freopen("lasers.in", "r", stdin);
    // freopen("lasers.out", "w", stdout);

    int t=1;
    while (t--){

        Nozarashi();
    }
    return 0;
}

Compilation message

mecho.cpp: In function 'long long int to_dec(std::string)':
mecho.cpp:45:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(long long  i=0;i<(s.size());i++){
      |                        ~^~~~~~~~~~~
mecho.cpp:43:9: warning: unused variable 'd' [-Wunused-variable]
   43 |     int d=0;
      |         ^

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	486 ms	6152 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	284 KB	Output is correct
12	Correct	2 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	3 ms	340 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	2 ms	340 KB	Output is correct
26	Correct	2 ms	340 KB	Output is correct
27	Correct	2 ms	340 KB	Output is correct
28	Correct	2 ms	340 KB	Output is correct
29	Correct	2 ms	340 KB	Output is correct
30	Correct	2 ms	340 KB	Output is correct
31	Correct	2 ms	340 KB	Output is correct
32	Correct	2 ms	340 KB	Output is correct
33	Correct	43 ms	1428 KB	Output is correct
34	Correct	42 ms	1364 KB	Output is correct
35	Correct	40 ms	1436 KB	Output is correct
36	Correct	58 ms	1760 KB	Output is correct
37	Correct	66 ms	1748 KB	Output is correct
38	Correct	52 ms	1756 KB	Output is correct
39	Correct	83 ms	2140 KB	Output is correct
40	Correct	70 ms	2132 KB	Output is correct
41	Correct	67 ms	2132 KB	Output is correct
42	Correct	86 ms	2580 KB	Output is correct
43	Correct	85 ms	2516 KB	Output is correct
44	Correct	87 ms	2516 KB	Output is correct
45	Correct	113 ms	3040 KB	Output is correct
46	Correct	106 ms	3028 KB	Output is correct
47	Correct	115 ms	3044 KB	Output is correct
48	Correct	126 ms	3576 KB	Output is correct
49	Correct	142 ms	3560 KB	Output is correct
50	Correct	147 ms	3560 KB	Output is correct
51	Correct	148 ms	4116 KB	Output is correct
52	Correct	146 ms	4052 KB	Output is correct
53	Correct	163 ms	4132 KB	Output is correct
54	Correct	169 ms	4692 KB	Output is correct
55	Correct	169 ms	4716 KB	Output is correct
56	Correct	170 ms	4708 KB	Output is correct
57	Correct	207 ms	5452 KB	Output is correct
58	Correct	209 ms	5352 KB	Output is correct
59	Correct	200 ms	5368 KB	Output is correct
60	Correct	216 ms	5972 KB	Output is correct
61	Correct	225 ms	6036 KB	Output is correct
62	Correct	241 ms	6040 KB	Output is correct
63	Correct	411 ms	6040 KB	Output is correct
64	Correct	501 ms	6040 KB	Output is correct
65	Correct	414 ms	6048 KB	Output is correct
66	Correct	418 ms	6060 KB	Output is correct
67	Correct	414 ms	6044 KB	Output is correct
68	Correct	446 ms	6068 KB	Output is correct
69	Correct	396 ms	6068 KB	Output is correct
70	Correct	450 ms	6064 KB	Output is correct
71	Correct	431 ms	6072 KB	Output is correct
72	Correct	454 ms	6100 KB	Output is correct
73	Correct	72 ms	6320 KB	Output is correct
74	Correct	472 ms	6312 KB	Output is correct
75	Correct	485 ms	6228 KB	Output is correct
76	Correct	473 ms	6228 KB	Output is correct
77	Correct	492 ms	6348 KB	Output is correct
78	Correct	436 ms	6272 KB	Output is correct
79	Correct	479 ms	6296 KB	Output is correct
80	Correct	453 ms	6288 KB	Output is correct
81	Correct	453 ms	6228 KB	Output is correct
82	Correct	433 ms	6288 KB	Output is correct
83	Correct	469 ms	6260 KB	Output is correct
84	Correct	484 ms	6252 KB	Output is correct
85	Correct	422 ms	6228 KB	Output is correct
86	Correct	483 ms	6252 KB	Output is correct
87	Correct	477 ms	6248 KB	Output is correct
88	Correct	461 ms	6220 KB	Output is correct
89	Correct	463 ms	6204 KB	Output is correct
90	Correct	462 ms	6204 KB	Output is correct
91	Correct	474 ms	6200 KB	Output is correct
92	Correct	456 ms	6204 KB	Output is correct