oj.uz

Submission #581479

# Submission time Handle Problem Language Result Execution time Memory
581479 2022-06-22T16:52:30 Z ansol4328 Robots (APIO13_robots) C++14
60 / 100
 1500 ms 114780 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];
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)
{
    map<int,vector<P>> Q;
    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){
                Q[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=Q[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;
                Q[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 38 ms 100024 KB Output is correct
2 Correct 38 ms 100052 KB Output is correct
3 Correct 44 ms 100128 KB Output is correct
4 Correct 42 ms 100144 KB Output is correct
5 Correct 39 ms 100172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 100024 KB Output is correct
2 Correct 38 ms 100052 KB Output is correct
3 Correct 44 ms 100128 KB Output is correct
4 Correct 42 ms 100144 KB Output is correct
5 Correct 39 ms 100172 KB Output is correct
6 Correct 49 ms 100128 KB Output is correct
7 Correct 44 ms 100016 KB Output is correct
8 Correct 42 ms 100116 KB Output is correct
9 Correct 48 ms 100036 KB Output is correct
10 Correct 41 ms 100084 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 100024 KB Output is correct
2 Correct 38 ms 100052 KB Output is correct
3 Correct 44 ms 100128 KB Output is correct
4 Correct 42 ms 100144 KB Output is correct
5 Correct 39 ms 100172 KB Output is correct
6 Correct 49 ms 100128 KB Output is correct
7 Correct 44 ms 100016 KB Output is correct
8 Correct 42 ms 100116 KB Output is correct
9 Correct 48 ms 100036 KB Output is correct
10 Correct 41 ms 100084 KB Output is correct
11 Correct 330 ms 105768 KB Output is correct
12 Correct 54 ms 105068 KB Output is correct
13 Correct 61 ms 105244 KB Output is correct
14 Correct 625 ms 106384 KB Output is correct
15 Correct 148 ms 105204 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 100024 KB Output is correct
2 Correct 38 ms 100052 KB Output is correct
3 Correct 44 ms 100128 KB Output is correct
4 Correct 42 ms 100144 KB Output is correct
5 Correct 39 ms 100172 KB Output is correct
6 Correct 49 ms 100128 KB Output is correct
7 Correct 44 ms 100016 KB Output is correct
8 Correct 42 ms 100116 KB Output is correct
9 Correct 48 ms 100036 KB Output is correct
10 Correct 41 ms 100084 KB Output is correct
11 Correct 330 ms 105768 KB Output is correct
12 Correct 54 ms 105068 KB Output is correct
13 Correct 61 ms 105244 KB Output is correct
14 Correct 625 ms 106384 KB Output is correct
15 Correct 148 ms 105204 KB Output is correct
16 Correct 128 ms 108312 KB Output is correct
17 Execution timed out 1580 ms 114780 KB Time limit exceeded
18 Halted 0 ms 0 KB -