oj.uz

답안 #578614

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
578614 2022-06-17T11:39:44 Z MohammadAghil 로봇 (APIO13_robots) C++17
60 / 100
 397 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 + 1, lg = 9, 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 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 0 ms 980 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 171 ms 77424 KB Output is correct
12 Correct 37 ms 71668 KB Output is correct
13 Correct 95 ms 72548 KB Output is correct
14 Correct 233 ms 80588 KB Output is correct
15 Correct 151 ms 73220 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 0 ms 980 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 171 ms 77424 KB Output is correct
12 Correct 37 ms 71668 KB Output is correct
13 Correct 95 ms 72548 KB Output is correct
14 Correct 233 ms 80588 KB Output is correct
15 Correct 151 ms 73220 KB Output is correct
16 Correct 368 ms 142512 KB Output is correct
17 Runtime error 397 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -