제출 #263360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
263360		atoiz	로봇 (APIO13_robots)	C++14	100 / 100	1014 ms	80736 KiB

robots

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40