oj.uz

Submission #862383

# Submission time Handle Problem Language Result Execution time Memory
862383 2023-10-18T07:32:03 Z noyancanturk Mecho (IOI09_mecho) C++17
10 / 100
 1000 ms 5292 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Execution timed out 1098 ms 3680 KB Time limit exceeded
8 Incorrect 1 ms 344 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Incorrect 2 ms 348 KB Output isn't correct
13 Incorrect 3 ms 344 KB Output isn't correct
14 Correct 5 ms 600 KB Output is correct
15 Incorrect 1 ms 348 KB Output isn't correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Incorrect 1 ms 348 KB Output isn't correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Incorrect 0 ms 348 KB Output isn't correct
25 Incorrect 1 ms 344 KB Output isn't correct
26 Incorrect 1 ms 348 KB Output isn't correct
27 Incorrect 1 ms 348 KB Output isn't correct
28 Incorrect 1 ms 348 KB Output isn't correct
29 Incorrect 1 ms 348 KB Output isn't correct
30 Incorrect 1 ms 348 KB Output isn't correct
31 Incorrect 1 ms 348 KB Output isn't correct
32 Incorrect 1 ms 348 KB Output isn't correct
33 Incorrect 34 ms 604 KB Output isn't correct
34 Incorrect 2 ms 604 KB Output isn't correct
35 Correct 136 ms 852 KB Output is correct
36 Incorrect 44 ms 860 KB Output isn't correct
37 Incorrect 2 ms 856 KB Output isn't correct
38 Correct 181 ms 860 KB Output is correct
39 Incorrect 67 ms 1080 KB Output isn't correct
40 Incorrect 3 ms 860 KB Output isn't correct
41 Correct 262 ms 1128 KB Output is correct
42 Incorrect 75 ms 1240 KB Output isn't correct
43 Incorrect 3 ms 1112 KB Output isn't correct
44 Correct 321 ms 1284 KB Output is correct
45 Incorrect 93 ms 1620 KB Output isn't correct
46 Incorrect 4 ms 1372 KB Output isn't correct
47 Correct 380 ms 1620 KB Output is correct
48 Incorrect 108 ms 1796 KB Output isn't correct
49 Incorrect 4 ms 1368 KB Output isn't correct
50 Correct 483 ms 1628 KB Output is correct
51 Incorrect 141 ms 1752 KB Output isn't correct
52 Incorrect 5 ms 1624 KB Output isn't correct
53 Correct 565 ms 2064 KB Output is correct
54 Incorrect 158 ms 2132 KB Output isn't correct
55 Incorrect 5 ms 1880 KB Output isn't correct
56 Correct 646 ms 2036 KB Output is correct
57 Incorrect 202 ms 2140 KB Output isn't correct
58 Incorrect 6 ms 2140 KB Output isn't correct
59 Correct 784 ms 2516 KB Output is correct
60 Incorrect 200 ms 2380 KB Output isn't correct
61 Incorrect 6 ms 2396 KB Output isn't correct
62 Correct 921 ms 2488 KB Output is correct
63 Correct 980 ms 2664 KB Output is correct
64 Incorrect 677 ms 2428 KB Output isn't correct
65 Execution timed out 1029 ms 2392 KB Time limit exceeded
66 Execution timed out 1039 ms 2428 KB Time limit exceeded
67 Execution timed out 1050 ms 2428 KB Time limit exceeded
68 Correct 775 ms 2648 KB Output is correct
69 Correct 548 ms 3064 KB Output is correct
70 Correct 824 ms 2672 KB Output is correct
71 Correct 932 ms 2660 KB Output is correct
72 Incorrect 643 ms 2896 KB Output isn't correct
73 Execution timed out 1049 ms 5036 KB Time limit exceeded
74 Execution timed out 1056 ms 5292 KB Time limit exceeded
75 Execution timed out 1050 ms 5040 KB Time limit exceeded
76 Execution timed out 1050 ms 4956 KB Time limit exceeded
77 Execution timed out 1065 ms 5032 KB Time limit exceeded
78 Execution timed out 1033 ms 4696 KB Time limit exceeded
79 Execution timed out 1034 ms 4764 KB Time limit exceeded
80 Execution timed out 1069 ms 4756 KB Time limit exceeded
81 Execution timed out 1035 ms 4696 KB Time limit exceeded
82 Execution timed out 1033 ms 4700 KB Time limit exceeded
83 Execution timed out 1055 ms 4188 KB Time limit exceeded
84 Execution timed out 1091 ms 4184 KB Time limit exceeded
85 Execution timed out 1030 ms 4332 KB Time limit exceeded
86 Execution timed out 1063 ms 4188 KB Time limit exceeded
87 Execution timed out 1025 ms 4184 KB Time limit exceeded
88 Execution timed out 1040 ms 3920 KB Time limit exceeded
89 Execution timed out 1018 ms 3924 KB Time limit exceeded
90 Execution timed out 1050 ms 3924 KB Time limit exceeded
91 Execution timed out 1029 ms 3928 KB Time limit exceeded
92 Execution timed out 1046 ms 3936 KB Time limit exceeded