| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 263290 |
2020-08-13T15:11:10 Z |
atoiz |
Robots (APIO13_robots) |
C++14 |
|
10 ms |
14208 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]);
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14208 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14208 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14208 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14208 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
