Submission #862383

#	Time	Username	Problem	Language	Result	Execution time	Memory
862383		noyancanturk	Mecho (IOI09_mecho)	C++17	10 / 100	1098 ms	5292 KiB

mecho

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
#endif
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define lim 1000001
using namespace std;
int mod=1000000007ll;

int n,s;
string g[802];
#define pii pair<int,int>
#define ppp pair<pii,pii>
pii bear;
vector<pii>hives;

bool check(int m){
    set<ppp>q;
    q.insert({{m*s,0},bear});
    bool infected[n+2][n+2];
    memset(infected,0,sizeof(infected));
    for(pii hive:hives){
        q.insert({{s,1},hive});
        infected[hive.first][hive.second]=1;
    }
    while(q.size()){
        auto [data,pos]=(*q.begin());
        q.erase(q.begin());
        if(g[pos.first][pos.second]=='D'){
            return 1;
        }
        if(data.second){
            //cerr<<"bee at "<<pos.first<<" "<<pos.second<<"\n";
            for(int x:{1,-1}){
                if(g[pos.first+x][pos.second]=='G'&&!infected[pos.first+x][pos.second]){
                    q.insert({{data.first+s,1},{pos.first+x,pos.second}});
                    infected[pos.first+x][pos.second]=1;
                }
                if(g[pos.first][pos.second+x]=='G'&&!infected[pos.first][pos.second+x]){
                    q.insert({{data.first+s,1},{pos.first,pos.second+x}});
                    infected[pos.first][pos.second+x]=1;
                }
            }
        }else if(!infected[pos.first][pos.second]){
            //cerr<<"at "<<pos.first<<" "<<pos.second<<"\n";
            for(int x:{1,-1}){
                if((g[pos.first+x][pos.second]=='G'||g[pos.first+x][pos.second]=='D')&&!infected[pos.first+x][pos.second]){
                    q.insert({{data.first+1,0},{pos.first+x,pos.second}});
                }//else cerr<<"oof "<<pos.first+x<<" "<<pos.second<<" "<<(g[pos.first+x][pos.second]=='G'||g[pos.first+x][pos.second]=='D')<<"\n";
                if(g[pos.first][pos.second+x]=='G'||g[pos.first][pos.second+x]=='D'&&!infected[pos.first][pos.second+x]){
                    q.insert({{data.first+1,0},{pos.first,pos.second+x}});
                }//else cerr<<"oof "<<pos.first<<" "<<pos.second+x<<" "<<(g[pos.first][pos.second+x]=='G'||g[pos.first][pos.second+x]=='D')<<"\n";
            }
        }
        infected[pos.first][pos.second]=1;
    }
    return 0;
}

void solve(){
    cin>>n>>s;
    g[0]=g[n+1]=string(n,'T');
    for(int i=1;i<=n;i++){
        cin>>g[i];
        g[i]="T"+g[i]+"T";
    }
    int count=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(g[i][j]=='G'){
                count++;
            }
            if(g[i][j]=='H'){
                hives.pb({i,j});
            }
            if(g[i][j]=='M'){
                bear={i,j};
            }
        }
    }
    int l=0,r=(count+s-1)/s,ans=-1;
    while(l<=r){
        //r=0;
        int m=(l+r)/2;
        if(check(m)){
            ans=m;
            l=m+1;
        }else{
            cerr<<"failed "<<m<<"\n";
            r=m-1;
        }
    }
    cout<<ans<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    /*
    freopen("atlarge.in","r",stdin);
    freopen("atlarge.out","w",stdout);
    */
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Compilation message (stderr)

mecho.cpp: In function 'bool check(long long int)':
mecho.cpp:51:84: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   51 |                 if(g[pos.first][pos.second+x]=='G'||g[pos.first][pos.second+x]=='D'&&!infected[pos.first][pos.second+x]){

• Subtask 1: 10 / 100