oj.uz

Submission #263365

# Submission time Handle Problem Language Result Execution time Memory
263365 2020-08-13T16:08:46 Z atoiz Robots (APIO13_robots) C++14
100 / 100
 809 ms 61048 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();
		if (curVal <= maxVal) curNode = a[curNode].nxt;
	}
} lis;

const int MAXN = 507, D[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}, INF = 1e8;
int N, R, C, nxt[MAXN][MAXN][4], dist[10][10][MAXN][MAXN];
bool inq[MAXN][MAXN];
string A[MAXN];
int qu[MAXN * MAXN * 4 + 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 << ' ' << R << ' ' << C << endl;
	if (x0 < 0 || x0 >= R || y0 < 0 || y0 >= C || A[x0][y0] == 'x') return cur = x * C + 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 >> C >> R;
	for (int x = 0; x < R; ++x) cin >> A[x];
	memset(nxt, -1, sizeof nxt);
	// cout << go(4, 4, 1) / C << ' ' << go(4, 4, 1) % C << endl;
	// return 0;

	for (int l = 1; l <= N; ++l) for (int r = l; r <= N; ++r) for (int x = 0; x < R; ++x) for (int y = 0; y < C; ++y) {
		dist[l][r][x][y] = INF;
	}
	for (int x = 0; x < R; ++x) for (int y = 0; y < C; ++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) {
		for (int l = 1; l <= N - range; ++l) {
			int r = l + range;

			lis.reset();
			for (int x = 0; x < R; ++x) for (int y = 0; y < C; ++y) {
				for (int m = l; m < r; ++m) {
					dist[l][r][x][y] = min(dist[l][r][x][y], dist[l][m][x][y] + dist[m + 1][r][x][y]);
				}

				if (dist[l][r][x][y] != INF) {
					lis.add(dist[l][r][x][y], x * C + y);
				}
			}	
			memset(inq, 0, sizeof inq);

			int qi = 0, sz = 0;
			auto upd = [&](int x0, int y0) {
				int d0 = dist[l][r][x0][y0];
				// cout << "upd " << l << ' ' << r << ' ' << x0 << ' ' << y0 << ": " << d0 << endl;
				for (int d = 0; d < 4; ++d) {
					int h1 = go(x0, y0, d), x1 = (h1 / C) % R, y1 = h1 % C;
					int &d1 = dist[l][r][x1][y1];
					if (d1 > d0 + 1) {
						d1 = d0 + 1;
						if (!inq[x1][y1]) {
							inq[x1][y1] = true;
							qu[sz++] = x1 * C + y1;
						}
					}
				}
			};
			while (true) {
				int h2 = lis.get(), x2 = h2 / C, y2 = h2 % C;
				int d2 = (h2 == -1 ? INF : dist[l][r][x2][y2]);

				for (; qi < sz; ++qi) {
					int h0 = qu[qi], x0 = h0 / C, y0 = h0 % C;
					int d0 = dist[l][r][x0][y0];
					if (d0 > d2) break;
					inq[x0][y0] = false;
					upd(x0, y0);
				}

				if (h2 == -1) break;
				lis.next();
				upd(x2, y2);
			}
		}
	}

	int ans = INF;
	for (int x = 0; x < R; ++x) for (int y = 0; y < C; ++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 11 ms 14464 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 14 ms 14464 KB Output is correct
4 Correct 14 ms 14464 KB Output is correct
5 Correct 14 ms 14592 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14464 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 14 ms 14464 KB Output is correct
4 Correct 14 ms 14464 KB Output is correct
5 Correct 14 ms 14592 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Correct 12 ms 14464 KB Output is correct
8 Correct 13 ms 14516 KB Output is correct
9 Correct 11 ms 14464 KB Output is correct
10 Correct 11 ms 14464 KB Output is correct
11 Correct 172 ms 41848 KB Output is correct
12 Correct 15 ms 15232 KB Output is correct
13 Correct 79 ms 31480 KB Output is correct
14 Correct 317 ms 41852 KB Output is correct
15 Correct 125 ms 41592 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14464 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 14 ms 14464 KB Output is correct
4 Correct 14 ms 14464 KB Output is correct
5 Correct 14 ms 14592 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Correct 12 ms 14464 KB Output is correct
8 Correct 13 ms 14516 KB Output is correct
9 Correct 11 ms 14464 KB Output is correct
10 Correct 11 ms 14464 KB Output is correct
11 Correct 172 ms 41848 KB Output is correct
12 Correct 15 ms 15232 KB Output is correct
13 Correct 79 ms 31480 KB Output is correct
14 Correct 317 ms 41852 KB Output is correct
15 Correct 125 ms 41592 KB Output is correct
16 Correct 142 ms 59580 KB Output is correct
17 Correct 809 ms 61048 KB Output is correct
18 Correct 217 ms 60284 KB Output is correct
19 Correct 162 ms 59700 KB Output is correct
20 Correct 513 ms 60408 KB Output is correct