oj.uz

답안 #578603

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
578603 2022-06-17T11:03:42 Z MohammadAghil 로봇 (APIO13_robots) C++17
60 / 100
 404 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;
               }
          }
     }

     rep(l,2,k+1){
          rep(i,0,k-l+1){
               int j = i + l - 1;
               vector<vector<pp>> pos(lg*n*m + 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]);
                         }
                    }
               }
          }
     }

     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 2 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 2 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 2 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 2 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 2 ms 2772 KB Output is correct
11 Correct 322 ms 86268 KB Output is correct
12 Correct 34 ms 64648 KB Output is correct
13 Correct 198 ms 86436 KB Output is correct
14 Correct 404 ms 86792 KB Output is correct
15 Correct 297 ms 85956 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 2 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 2 ms 2772 KB Output is correct
11 Correct 322 ms 86268 KB Output is correct
12 Correct 34 ms 64648 KB Output is correct
13 Correct 198 ms 86436 KB Output is correct
14 Correct 404 ms 86792 KB Output is correct
15 Correct 297 ms 85956 KB Output is correct
16 Runtime error 98 ms 163840 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -