oj.uz

Submission #581488

# Submission time Handle Problem Language Result Execution time Memory
581488 2022-06-22T17:02:20 Z ansol4328 Robots (APIO13_robots) C++14
60 / 100
 205 ms 163840 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct A{
    int y, x, dir;
};

int n, w, h;
string xy[505];
P nxt[505][505][4];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int D[10][10][505][505];
vector<P> nQ[250000*8+5];
const int INF=1e9;

void fastio(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
}

void get_nxt()
{
    queue<A> Q;
    for(int i=0 ; i<h ; i++){
        for(int j=0 ; j<w ; j++){
            if(xy[i][j]=='x') continue;
            for(int k=0 ; k<4 ; k++){
                nxt[i][j][k]=P(-1,-1);
                int ny=i+dy[k], nx=j+dx[k];
                if(ny<0 || ny>=h || nx<0 || nx>=w || xy[ny][nx]=='x'){
                    nxt[i][j][k]=P(i,j);
                    Q.push({i,j,k});
                }
            }
        }
    }
    while(!Q.empty()){
        A v=Q.front(); Q.pop();
        P pr=nxt[v.y][v.x][v.dir];
        if(xy[v.y][v.x]=='A') v.dir=(v.dir+1)%4;
        else if(xy[v.y][v.x]=='C') v.dir=(v.dir+3)%4;
        v.dir=(v.dir+2)%4;
        v.y+=dy[v.dir], v.x+=dx[v.dir];
        if(v.y<0 || v.y>=h || v.x<0 || v.x>=w || xy[v.y][v.x]=='x') continue;
        v.dir=(v.dir+2)%4;
        nxt[v.y][v.x][v.dir]=pr; Q.push(v);
    }
}

void prop(int s, int e)
{
    vector<vector<bool>> chk(h,vector<bool>(w));
    int mn=INF, mx=0;
    for(int i=0 ; i<h ; i++){
        for(int j=0 ; j<w ; j++){
            if(D[s][e][i][j]!=-1) mn=min(mn,D[s][e][i][j]), mx=max(mx,D[s][e][i][j]);
        }
    }
    for(int i=mn ; i<=min(250000*8+4,mx+w*h) ; i++) nQ[i].clear();
    for(int i=0 ; i<h ; i++){
        for(int j=0 ; j<w ; j++){
            if(D[s][e][i][j]!=-1){
                nQ[D[s][e][i][j]].pb(P(i,j));
                mn=min(mn,D[s][e][i][j]);
                mx=max(mx,D[s][e][i][j]);
            }
        }
    }
    while(mn<=mx){
        vector<P> &cur=nQ[mn];
        if(cur.empty()){
            mn++; continue;
        }
        P v=cur.back(); cur.pop_back();
        if(chk[v.fi][v.se]) continue;
        chk[v.fi][v.se]=true;
        for(int i=0 ; i<4 ; i++){
            if(nxt[v.fi][v.se][i]==P(-1,-1)) continue;
            P nv=nxt[v.fi][v.se][i];
            if(!chk[nv.fi][nv.se] && (D[s][e][nv.fi][nv.se]==-1 || D[s][e][nv.fi][nv.se]>D[s][e][v.fi][v.se]+1)){
                D[s][e][nv.fi][nv.se]=D[s][e][v.fi][v.se]+1;
                nQ[D[s][e][nv.fi][nv.se]].pb(nv);
                mx=max(mx,D[s][e][nv.fi][nv.se]);
            }
        }
    }
}

int main()
{
    fastio();
    cin >> n >> w >> h;
    for(int i=0 ; i<h ; i++) cin >> xy[i];
    get_nxt();
    memset(D,-1,sizeof(D));
    for(int i=0 ; i<h ; i++){
        for(int j=0 ; j<w ; j++){
            if(xy[i][j]>='1' && xy[i][j]<='9'){
                D[xy[i][j]-'0'][xy[i][j]-'0'][i][j]=0;
                prop(xy[i][j]-'0',xy[i][j]-'0');
            }
        }
    }
    /*
        for(int i=1, j=1 ; i<=n ; i++, j++){
            cout << "[ " << i << ' ' << j << " ]\n";
            for(int y=0 ; y<h ; y++){
                for(int x=0 ; x<w ; x++){
                    cout << D[i][j][y][x] << ' ';
                }
                cout << '\n';
            }
        }
    */
    for(int x=1 ; x<n ; x++){
        for(int i=1, j=1+x ; i+x<=n ; i++, j++){
            for(int c=i ; c<j ; c++){
                for(int y=0 ; y<h ; y++){
                    for(int x=0 ; x<w ; x++){
                        if(D[i][c][y][x]==-1 || D[c+1][j][y][x]==-1) continue;
                        if(D[i][j][y][x]==-1 || D[i][j][y][x]>D[i][c][y][x]+D[c+1][j][y][x]) D[i][j][y][x]=D[i][c][y][x]+D[c+1][j][y][x];
                    }
                }
            }
            prop(i,j);
            /*
            cout << "[ " << i << ' ' << j << " ]\n";
            for(int y=0 ; y<h ; y++){
                for(int x=0 ; x<w ; x++){
                    cout << D[i][j][y][x] << ' ';
                }
                cout << '\n';
            }
            */
        }
    }
    int ans=-1;
    for(int i=0 ; i<h ; i++) for(int j=0 ; j<w ; j++) if(D[1][n][i][j]!=-1 && (ans==-1 || ans>D[1][n][i][j])) ans=D[1][n][i][j];
    cout << ans;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147020 KB Output is correct
2 Correct 61 ms 147056 KB Output is correct
3 Correct 62 ms 147016 KB Output is correct
4 Correct 62 ms 147072 KB Output is correct
5 Correct 62 ms 147020 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147020 KB Output is correct
2 Correct 61 ms 147056 KB Output is correct
3 Correct 62 ms 147016 KB Output is correct
4 Correct 62 ms 147072 KB Output is correct
5 Correct 62 ms 147020 KB Output is correct
6 Correct 61 ms 147056 KB Output is correct
7 Correct 60 ms 147016 KB Output is correct
8 Correct 59 ms 147040 KB Output is correct
9 Correct 59 ms 147144 KB Output is correct
10 Correct 58 ms 147128 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147020 KB Output is correct
2 Correct 61 ms 147056 KB Output is correct
3 Correct 62 ms 147016 KB Output is correct
4 Correct 62 ms 147072 KB Output is correct
5 Correct 62 ms 147020 KB Output is correct
6 Correct 61 ms 147056 KB Output is correct
7 Correct 60 ms 147016 KB Output is correct
8 Correct 59 ms 147040 KB Output is correct
9 Correct 59 ms 147144 KB Output is correct
10 Correct 58 ms 147128 KB Output is correct
11 Correct 127 ms 154324 KB Output is correct
12 Correct 67 ms 151204 KB Output is correct
13 Correct 76 ms 152292 KB Output is correct
14 Correct 205 ms 159484 KB Output is correct
15 Correct 110 ms 151620 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147020 KB Output is correct
2 Correct 61 ms 147056 KB Output is correct
3 Correct 62 ms 147016 KB Output is correct
4 Correct 62 ms 147072 KB Output is correct
5 Correct 62 ms 147020 KB Output is correct
6 Correct 61 ms 147056 KB Output is correct
7 Correct 60 ms 147016 KB Output is correct
8 Correct 59 ms 147040 KB Output is correct
9 Correct 59 ms 147144 KB Output is correct
10 Correct 58 ms 147128 KB Output is correct
11 Correct 127 ms 154324 KB Output is correct
12 Correct 67 ms 151204 KB Output is correct
13 Correct 76 ms 152292 KB Output is correct
14 Correct 205 ms 159484 KB Output is correct
15 Correct 110 ms 151620 KB Output is correct
16 Correct 141 ms 155388 KB Output is correct
17 Runtime error 174 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -