Submission #885980

#TimeUsernameProblemLanguageResultExecution timeMemory
885980JakobZorzMecho (IOI09_mecho)C++17
100 / 100
905 ms3328 KiB
#include<iostream> #include<vector> #include<queue> #include<stack> #include<algorithm> #include<limits.h> #include<math.h> #include<map> #include<set> #include<unordered_map> #include<unordered_set> #include<iomanip> #include<cstring> typedef long long ll; typedef unsigned long long ull; typedef long double ld; using namespace std; //const int MOD=1e9+7; //typedef pair<ll,ll>Point; //typedef pair<ll,ll>Line; //#define x first //#define y second int n,s; vector<string>m,cm; vector<pair<int,int>>q1,q2; vector<pair<int,int>>get_nbs(pair<int,int>pos){ vector<pair<int,int>>res; if(pos.first!=0) res.emplace_back(pos.first-1,pos.second); if(pos.second!=0) res.emplace_back(pos.first,pos.second-1); if(pos.first!=n-1) res.emplace_back(pos.first+1,pos.second); if(pos.second!=n-1) res.emplace_back(pos.first,pos.second+1); return res; } void spread_bees(){ vector<pair<int,int>>q; for(pair<int,int>curr:q2){ vector<pair<int,int>>nbs=get_nbs(curr); for(pair<int,int>i:nbs){ if(cm[i.first][i.second]=='H') continue; if(cm[i.first][i.second]=='T') continue; if(cm[i.first][i.second]=='D') continue; cm[i.first][i.second]='H'; q.push_back(i); } } q2=q; } bool check(int waits){ cm=m; q1.clear(); q2.clear(); for(int x=0;x<n;x++) for(int y=0;y<n;y++){ if(cm[x][y]=='H') q2.emplace_back(x,y); if(cm[x][y]=='M') q1.emplace_back(x,y); } while(waits--&&q2.size()){ spread_bees(); } while(q1.size()){ for(int i=0;i<s;i++){ vector<pair<int,int>>q; for(pair<int,int>curr:q1){ if(cm[curr.first][curr.second]!='M') continue; vector<pair<int,int>>nbs=get_nbs(curr); for(pair<int,int>i:nbs){ if(cm[i.first][i.second]=='H') continue; if(cm[i.first][i.second]=='T') continue; if(cm[i.first][i.second]=='D') return true; if(cm[i.first][i.second]=='M') continue; cm[i.first][i.second]='M'; q.push_back(i); } } q1=q; } spread_bees(); } return false; } void solve(){ cin>>n>>s; m.resize(n); for(string&i:m) cin>>i; int l=-1,r=4e5; while(l<r-1){ int m=(l+r)/2; if(check(m)) l=m; else r=m; } cout<<l<<"\n"; } int main(){ ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL); //freopen("bank.in","r",stdin);freopen("bank.out","w",stdout); int t=1;//cin>>t; while(t--)solve(); return 0; } /* 7 3 TTTTTTT TGGGGGT TGGGGGT MGGGGGD TGGGGGT TGGGGGT THHHHHT 7 3 TTTTTTT TGGGGGT TGGGGGT MGGGGGD TGGGGGT TGGGGGT TGHHGGT */
#Verdict Execution timeMemoryGrader output
Fetching results...