oj.uz

답안 #578612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
578612 2022-06-17T11:38:27 Z MohammadAghil 로봇 (APIO13_robots) C++17
60 / 100
 255 ms 163840 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e2 + 5, lg = 10, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
 
int st[maxn][maxn], n, m, k;
pp ply[lg], adj[maxn][maxn][4];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool vis[maxn][maxn][4];
int dist[lg][lg][maxn][maxn];
 
pp dfs(int x, int y, int dir){
     if(vis[x][y][dir]) return adj[x][y][dir];
     adj[x][y][dir] = {-1, -1};
     vis[x][y][dir] = true;
     int d = dir;
     if(st[x][y] == 2) d = (d + 3)%4;
     if(st[x][y] == 3) d = (d + 1)%4;
     int i = x + dx[d], j = y + dy[d];
     if(i < 0 || i == n || j < 0 || j == m || !st[i][j]) return adj[x][y][dir] = {x, y};
     return adj[x][y][dir] = dfs(i, j, d);
}
 
int main(){
     cin.tie(0) -> sync_with_stdio(0);
     cin >> k >> m >> n;
     rep(i,0,n) rep(j,0,m){
          char c; cin >> c;
          if(c == '.') st[i][j] = 1;
          if(c == 'A') st[i][j] = 2;
          if(c == 'C') st[i][j] = 3;
          if(c >= '0' && c <= '9') st[i][j] = 1, ply[c-'1'] = {i, j};
     }
     rep(i,0,n) rep(j,0,m) rep(d,0,4) dfs(i, j, d);
 
     rep(i,0,lg) rep(j,0,lg) rep(t,0,n) rep(f,0,m) dist[i][j][t][f] = inf;
 
     rep(t,0,k){
          deque<pp> q{ply[t]}; dist[t][t][ply[t].ff][ply[t].ss] = 0;
          while(sz(q)){
               auto[x, y] = q.front(); q.pop_front();
               rep(d,0,4) if(adj[x][y][d].ff + 1 && dist[t][t][adj[x][y][d].ff][adj[x][y][d].ss] == inf){
                    q.push_back(adj[x][y][d]);
                    dist[t][t][adj[x][y][d].ff][adj[x][y][d].ss] = dist[t][t][x][y] + 1;
               }
          }
     }
 
     vector<vector<pp>> pos(lg*n*m + 1);
     rep(l,2,k+1){
          rep(i,0,k-l+1){
               int j = i + l - 1;
               // priority_queue<pair<int, pp>, vector<pair<int, pp>>, greater<pair<int, pp>>> q;
               rep(x,0,n) rep(y,0,m){
                    rep(m,i,j){
                         dist[i][j][x][y] = min(dist[i][j][x][y], dist[i][m][x][y] + dist[m+1][j][x][y]);
                    }
                    if(dist[i][j][x][y] - inf) pos[dist[i][j][x][y]].pb({x, y});
                    dist[i][j][x][y] = inf;
               }
 
               // while(sz(q)){
               //      auto[w, t] = q.top(); q.pop();
               //      auto[x, y] = t;
               //      if(w - dist[i][j][x][y]) continue;
               //      rep(d,0,4){
               //           auto[xp, yp] = adj[x][y][d];
               //           if(xp + 1 && dist[i][j][xp][yp] > w + 1){
               //                q.push({dist[i][j][xp][yp] = w + 1, {xp, yp}});
               //           }
               //      }
               // }
 
               rep(s,0,sz(pos)){
                    for(auto[x, y]: pos[s]) if(dist[i][j][x][y] == inf){
                         dist[i][j][x][y] = s;
                         rep(d,0,4) if(adj[x][y][d].ff + 1 && dist[i][j][adj[x][y][d].ff][adj[x][y][d].ss] == inf){
                              pos[s + 1].pb(adj[x][y][d]);
                         }
                    }
                    pos[s].clear();
               }
          }
     }
 
     int ans = inf;
     rep(i,0,n) rep(j,0,m) ans = min(ans, dist[0][k-1][i][j]);
     cout << (ans == inf? -1: ans) << '\n';
     return 0; 
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 1 ms 2772 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 1 ms 2772 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 2772 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 1 ms 2772 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 2772 KB Output is correct
11 Correct 209 ms 91076 KB Output is correct
12 Correct 48 ms 85392 KB Output is correct
13 Correct 118 ms 86372 KB Output is correct
14 Correct 255 ms 94436 KB Output is correct
15 Correct 170 ms 87044 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 1 ms 2772 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 2772 KB Output is correct
11 Correct 209 ms 91076 KB Output is correct
12 Correct 48 ms 85392 KB Output is correct
13 Correct 118 ms 86372 KB Output is correct
14 Correct 255 ms 94436 KB Output is correct
15 Correct 170 ms 87044 KB Output is correct
16 Runtime error 93 ms 163840 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -