oj.uz

Submission #263360

# Submission time Handle Problem Language Result Execution time Memory
263360 2020-08-13T16:07:31 Z atoiz Robots (APIO13_robots) C++14
100 / 100
 1014 ms 80736 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14208 KB Output is correct
2 Correct 10 ms 14208 KB Output is correct
3 Correct 9 ms 14208 KB Output is correct
4 Correct 13 ms 14336 KB Output is correct
5 Correct 9 ms 14336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14208 KB Output is correct
2 Correct 10 ms 14208 KB Output is correct
3 Correct 9 ms 14208 KB Output is correct
4 Correct 13 ms 14336 KB Output is correct
5 Correct 9 ms 14336 KB Output is correct
6 Correct 14 ms 14208 KB Output is correct
7 Correct 11 ms 14208 KB Output is correct
8 Correct 10 ms 14208 KB Output is correct
9 Correct 10 ms 14208 KB Output is correct
10 Correct 10 ms 14336 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14208 KB Output is correct
2 Correct 10 ms 14208 KB Output is correct
3 Correct 9 ms 14208 KB Output is correct
4 Correct 13 ms 14336 KB Output is correct
5 Correct 9 ms 14336 KB Output is correct
6 Correct 14 ms 14208 KB Output is correct
7 Correct 11 ms 14208 KB Output is correct
8 Correct 10 ms 14208 KB Output is correct
9 Correct 10 ms 14208 KB Output is correct
10 Correct 10 ms 14336 KB Output is correct
11 Correct 138 ms 48504 KB Output is correct
12 Correct 17 ms 15744 KB Output is correct
13 Correct 43 ms 35460 KB Output is correct
14 Correct 363 ms 50808 KB Output is correct
15 Correct 100 ms 47864 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14208 KB Output is correct
2 Correct 10 ms 14208 KB Output is correct
3 Correct 9 ms 14208 KB Output is correct
4 Correct 13 ms 14336 KB Output is correct
5 Correct 9 ms 14336 KB Output is correct
6 Correct 14 ms 14208 KB Output is correct
7 Correct 11 ms 14208 KB Output is correct
8 Correct 10 ms 14208 KB Output is correct
9 Correct 10 ms 14208 KB Output is correct
10 Correct 10 ms 14336 KB Output is correct
11 Correct 138 ms 48504 KB Output is correct
12 Correct 17 ms 15744 KB Output is correct
13 Correct 43 ms 35460 KB Output is correct
14 Correct 363 ms 50808 KB Output is correct
15 Correct 100 ms 47864 KB Output is correct
16 Correct 110 ms 68600 KB Output is correct
17 Correct 1014 ms 80736 KB Output is correct
18 Correct 208 ms 72336 KB Output is correct
19 Correct 114 ms 68680 KB Output is correct
20 Correct 608 ms 76536 KB Output is correct