제출 #777246

#제출 시각아이디문제언어결과실행 시간메모리
777246_ZeyadRafatMecho (IOI09_mecho)C++14
100 / 100
501 ms6348 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...