Submission #1031696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031696		ezzzay	Mecho (IOI09_mecho)	C++14	2 / 100	1098 ms	4572 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=1000;
char arr[N][N];
bool vis[N][N];
int xx[4]={1,-1,0,0};
int yy[4]={0,0,-1,1};
int sx,sy,fx,fy;
char brr[N][N],crr[N][N];
int n,s;
void dfs(int y, int x){
    vis[y][x]=1;
    for(int i=0;i<4;i++){
        if((brr[y+yy[i]][x+xx[i]]=='G' or brr[y+yy[i]][x+xx[i]]=='D') and vis[y+yy[i]][x+xx[i]]==0 ){
            dfs(y+yy[i],x+xx[i]);
        }
    }
}
bool check(int t){
    int h=t;
    while(h--){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                crr[i][j]=brr[i][j];
                vis[i][j]=0;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int k=0;k<4;k++){
                    if(crr[i+yy[k]][j+xx[k]]=='G' and crr[i][j]=='H'){
                        brr[i+yy[k]][j+xx[k]]='H';
                    }
                }
            }
        }
    }
    vis[sy][sx]=1;
    dfs(sy,sx);
    return vis[fy][fx];
}
signed main(){
   
    cin>>n>>s;
   
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>arr[i][j];
            if(arr[i][j]=='M'){
                sy=i;
                sx=j;
            }
            if(arr[i][j]=='D'){
                fy=i;
                fx=j;
            }
        }
    }
    
    int lo=0,hi=10000;
     
    while(hi>=lo){
        int mid=(hi+lo)/2;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                brr[i][j]=arr[i][j];
            }
        }
        if(check(mid)){
            lo=mid+1;
        }
        else{
            hi=mid-1;
        }
    }
    cout<<hi-2;
}

Compilation message (stderr)

mecho.cpp: In function 'bool check(long long int)':
mecho.cpp:36:46: warning: writing 1 byte into a region of size 0 [-Wstringop-overflow=]
   36 |                         brr[i+yy[k]][j+xx[k]]='H';
      |                         ~~~~~~~~~~~~~~~~~~~~~^~~~
mecho.cpp:13:6: note: at offset 0 to object 'brr' with size 1000000 declared here
   13 | char brr[N][N],crr[N][N];
      |      ^~~

• Subtask 1: 2 / 100