제출 #263360

#제출 시각아이디문제언어결과실행 시간메모리
263360atoiz로봇 (APIO13_robots)C++14
100 / 100
1014 ms80736 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> using namespace std; struct MultiList { using data_t = int; static const data_t FAIL = -1; static const int MAX_VAL = 500 * 500 * 10 + 1000, MAX_NODES = 500 * 500 * 10 + 1000; int start[MAX_VAL]; struct node { int nxt; data_t data; } a[MAX_NODES]; int cntNodes, maxVal, curVal, curNode; void reset() { memset(start, 0, sizeof start); cntNodes = 0, maxVal = 0, curVal = -1, curNode = 0; } void add(int val, data_t data) { a[++cntNodes] = {start[val], data}; start[val] = cntNodes; maxVal = max(maxVal, val); } void normalize() { if (curNode == 0) { for (++curVal; curVal <= maxVal && !start[curVal]; ++curVal); if (curVal <= maxVal) curNode = start[curVal]; } } data_t get() { normalize(); if (curVal > maxVal) return FAIL; data_t data = a[curNode].data; return data; } void next() { normalize(); curNode = a[curNode].nxt; } } lis; const int MAXN = 507, D[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}, INF = 1e8; int N, W, H, nxt[MAXN][MAXN][4], dist[10][10][MAXN][MAXN], inq[10][MAXN][MAXN]; string A[MAXN]; int qu[MAXN * MAXN * 4 * 10 + 100]; int go(int x, int y, int d) { int &cur = nxt[x][y][d]; if (~cur) return cur; int x0 = x + D[d][0], y0 = y + D[d][1]; // cout << x << ' ' << y << ' ' << x0 << ' ' << y0 << ' ' << W << ' ' << H << endl; if (x0 < 0 || x0 >= W || y0 < 0 || y0 >= H || A[x0][y0] == 'x') return cur = x * H + y; if (A[x0][y0] == 'A') d = (d + 3) % 4; if (A[x0][y0] == 'C') d = (d + 1) % 4; return cur = go(x0, y0, d); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> H >> W; for (int x = 0; x < W; ++x) cin >> A[x]; memset(nxt, -1, sizeof nxt); // cout << go(4, 4, 1) / H << ' ' << go(4, 4, 1) % H << endl; // return 0; for (int l = 1; l <= N; ++l) for (int r = l; r <= N; ++r) for (int x = 0; x < W; ++x) for (int y = 0; y < H; ++y) { dist[l][r][x][y] = INF; } for (int x = 0; x < W; ++x) for (int y = 0; y < H; ++y) if ('1' <= A[x][y] && A[x][y] <= '9') { dist[A[x][y] - '0'][A[x][y] - '0'][x][y] = 0; } for (int range = 0; range < N; ++range) { lis.reset(); for (int l = 1; l <= N - range; ++l) { for (int x = 0; x < W; ++x) for (int y = 0; y < H; ++y) { for (int m = l; m < l + range; ++m) { dist[l][l + range][x][y] = min(dist[l][l + range][x][y], dist[l][m][x][y] + dist[m + 1][l + range][x][y]); } if (dist[l][l + range][x][y] != INF) { lis.add(dist[l][l + range][x][y], l * W * H + x * H + y); } inq[l][x][y] = false; } } int qi = 0, sz = 0; auto upd = [&](int l0, int x0, int y0) { int d0 = dist[l0][l0 + range][x0][y0]; // cout << "upd " << l0 << ' ' << l0 + range << ' ' << x0 << ' ' << y0 << ": " << d0 << endl; for (int d = 0; d < 4; ++d) { int h1 = go(x0, y0, d), x1 = (h1 / H) % W, y1 = h1 % H; int &d1 = dist[l0][l0 + range][x1][y1]; if (d1 > d0 + 1) { d1 = d0 + 1; if (!inq[l0][x1][y1]) { inq[l0][x1][y1] = true; qu[sz++] = l0 * W * H + x1 * H + y1; } } } }; while (true) { int h2 = lis.get(), l2 = (h2 / (W * H)), x2 = (h2 / H) % W, y2 = h2 % H; int d2 = (h2 == -1 ? INF : dist[l2][l2 + range][x2][y2]); lis.next(); for (; qi < sz; ++qi) { int h0 = qu[qi], l0 = (h0 / (W * H)), x0 = (h0 / H) % W, y0 = h0 % H; int d0 = dist[l0][l0 + range][x0][y0]; if (d0 > d2) break; inq[l0][x0][y0] = false; upd(l0, x0, y0); } if (h2 == -1) break; upd(l2, x2, y2); } } int ans = INF; for (int x = 0; x < W; ++x) for (int y = 0; y < H; ++y) { ans = min(ans, dist[1][N][x][y]); } if (ans == INF) ans = -1; cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...