oj.uz

Submission #862382

# Submission time Handle Problem Language Result Execution time Memory
862382 2023-10-18T07:30:21 Z noyancanturk Mecho (IOI09_mecho) C++17
19 / 100
 1000 ms 5716 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,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
19.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 1 ms 480 KB Output isn't correct
4 Incorrect 0 ms 480 KB Output isn't correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Execution timed out 1092 ms 4024 KB Time limit exceeded
8 Incorrect 1 ms 344 KB Output isn't correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Incorrect 2 ms 348 KB Output isn't correct
13 Incorrect 4 ms 348 KB Output isn't correct
14 Correct 6 ms 344 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Correct 1 ms 480 KB Output is correct
19 Incorrect 0 ms 480 KB Output isn't correct
20 Correct 1 ms 348 KB Output is correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Correct 1 ms 348 KB Output is correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Correct 1 ms 348 KB Output is correct
25 Incorrect 1 ms 348 KB Output isn't correct
26 Correct 1 ms 348 KB Output is correct
27 Incorrect 1 ms 344 KB Output isn't correct
28 Correct 2 ms 348 KB Output is correct
29 Incorrect 1 ms 348 KB Output isn't correct
30 Correct 2 ms 480 KB Output is correct
31 Incorrect 1 ms 348 KB Output isn't correct
32 Correct 2 ms 348 KB Output is correct
33 Incorrect 31 ms 860 KB Output isn't correct
34 Correct 48 ms 860 KB Output is correct
35 Correct 211 ms 988 KB Output is correct
36 Incorrect 45 ms 1116 KB Output isn't correct
37 Correct 66 ms 1112 KB Output is correct
38 Correct 298 ms 1148 KB Output is correct
39 Incorrect 55 ms 1116 KB Output isn't correct
40 Correct 83 ms 1116 KB Output is correct
41 Correct 370 ms 1324 KB Output is correct
42 Incorrect 70 ms 1368 KB Output isn't correct
43 Correct 100 ms 1468 KB Output is correct
44 Correct 471 ms 1620 KB Output is correct
45 Incorrect 89 ms 1668 KB Output isn't correct
46 Correct 123 ms 1668 KB Output is correct
47 Correct 590 ms 1876 KB Output is correct
48 Incorrect 99 ms 1904 KB Output isn't correct
49 Correct 162 ms 1904 KB Output is correct
50 Correct 708 ms 1880 KB Output is correct
51 Incorrect 123 ms 2140 KB Output isn't correct
52 Correct 177 ms 2144 KB Output is correct
53 Correct 844 ms 2464 KB Output is correct
54 Incorrect 145 ms 2412 KB Output isn't correct
55 Correct 217 ms 2416 KB Output is correct
56 Correct 974 ms 2740 KB Output is correct
57 Incorrect 178 ms 2648 KB Output isn't correct
58 Correct 248 ms 2704 KB Output is correct
59 Execution timed out 1010 ms 2648 KB Time limit exceeded
60 Incorrect 195 ms 3012 KB Output isn't correct
61 Correct 280 ms 3008 KB Output is correct
62 Execution timed out 1055 ms 3156 KB Time limit exceeded
63 Execution timed out 1024 ms 3040 KB Time limit exceeded
64 Execution timed out 1028 ms 3020 KB Time limit exceeded
65 Execution timed out 1037 ms 2908 KB Time limit exceeded
66 Execution timed out 1066 ms 3056 KB Time limit exceeded
67 Execution timed out 1058 ms 3052 KB Time limit exceeded
68 Execution timed out 1051 ms 3292 KB Time limit exceeded
69 Execution timed out 1025 ms 3296 KB Time limit exceeded
70 Execution timed out 1048 ms 3180 KB Time limit exceeded
71 Execution timed out 1048 ms 3300 KB Time limit exceeded
72 Execution timed out 1068 ms 3164 KB Time limit exceeded
73 Execution timed out 1050 ms 5716 KB Time limit exceeded
74 Execution timed out 1020 ms 5456 KB Time limit exceeded
75 Execution timed out 1030 ms 5456 KB Time limit exceeded
76 Execution timed out 1030 ms 5648 KB Time limit exceeded
77 Execution timed out 1053 ms 5468 KB Time limit exceeded
78 Execution timed out 1073 ms 5212 KB Time limit exceeded
79 Execution timed out 1066 ms 5212 KB Time limit exceeded
80 Execution timed out 1045 ms 5200 KB Time limit exceeded
81 Execution timed out 1060 ms 5212 KB Time limit exceeded
82 Execution timed out 1065 ms 5212 KB Time limit exceeded
83 Execution timed out 1041 ms 4944 KB Time limit exceeded
84 Execution timed out 1018 ms 4944 KB Time limit exceeded
85 Execution timed out 1061 ms 4944 KB Time limit exceeded
86 Execution timed out 1053 ms 4956 KB Time limit exceeded
87 Execution timed out 1071 ms 4948 KB Time limit exceeded
88 Execution timed out 1043 ms 4440 KB Time limit exceeded
89 Execution timed out 1018 ms 4952 KB Time limit exceeded
90 Execution timed out 1073 ms 4444 KB Time limit exceeded
91 Execution timed out 1100 ms 4432 KB Time limit exceeded
92 Execution timed out 1051 ms 4496 KB Time limit exceeded