oj.uz

Submission #263379

# Submission time Handle Problem Language Result Execution time Memory
263379 2020-08-13T16:20:13 Z atoiz Robots (APIO13_robots) C++14
100 / 100
 1079 ms 120228 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;

	vector<data_t> vec[MAX_VAL];

	int maxVal, curVal;

	void reset()
	{
		curVal = maxVal = 0;
		for (int i = 0; i < MAX_VAL; ++i) vec[i].clear();
	}

	void add(int val, data_t data)
	{
		vec[val].push_back(data);
		maxVal = max(maxVal, val);
	}

	void normalize()
	{
		if (vec[curVal].empty()) {
			for (++curVal; curVal <= maxVal && vec[curVal].empty(); ++curVal);
		}
	}	

	data_t get()
	{
		normalize();
		if (curVal > maxVal) return FAIL;
		return vec[curVal].back();
	}

	void next()
	{
		normalize();
		if (curVal <= maxVal) vec[curVal].pop_back();
	}
} 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) {
			lis.reset();
			int r = l + range;

			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 60 ms 63352 KB Output is correct
2 Correct 57 ms 63352 KB Output is correct
3 Correct 57 ms 63360 KB Output is correct
4 Correct 61 ms 63480 KB Output is correct
5 Correct 58 ms 63480 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 63352 KB Output is correct
2 Correct 57 ms 63352 KB Output is correct
3 Correct 57 ms 63360 KB Output is correct
4 Correct 61 ms 63480 KB Output is correct
5 Correct 58 ms 63480 KB Output is correct
6 Correct 59 ms 63352 KB Output is correct
7 Correct 58 ms 63352 KB Output is correct
8 Correct 64 ms 63480 KB Output is correct
9 Correct 58 ms 63356 KB Output is correct
10 Correct 58 ms 63480 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 63352 KB Output is correct
2 Correct 57 ms 63352 KB Output is correct
3 Correct 57 ms 63360 KB Output is correct
4 Correct 61 ms 63480 KB Output is correct
5 Correct 58 ms 63480 KB Output is correct
6 Correct 59 ms 63352 KB Output is correct
7 Correct 58 ms 63352 KB Output is correct
8 Correct 64 ms 63480 KB Output is correct
9 Correct 58 ms 63356 KB Output is correct
10 Correct 58 ms 63480 KB Output is correct
11 Correct 402 ms 92904 KB Output is correct
12 Correct 51 ms 64248 KB Output is correct
13 Correct 213 ms 80504 KB Output is correct
14 Correct 584 ms 93816 KB Output is correct
15 Correct 366 ms 91132 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 63352 KB Output is correct
2 Correct 57 ms 63352 KB Output is correct
3 Correct 57 ms 63360 KB Output is correct
4 Correct 61 ms 63480 KB Output is correct
5 Correct 58 ms 63480 KB Output is correct
6 Correct 59 ms 63352 KB Output is correct
7 Correct 58 ms 63352 KB Output is correct
8 Correct 64 ms 63480 KB Output is correct
9 Correct 58 ms 63356 KB Output is correct
10 Correct 58 ms 63480 KB Output is correct
11 Correct 402 ms 92904 KB Output is correct
12 Correct 51 ms 64248 KB Output is correct
13 Correct 213 ms 80504 KB Output is correct
14 Correct 584 ms 93816 KB Output is correct
15 Correct 366 ms 91132 KB Output is correct
16 Correct 358 ms 108656 KB Output is correct
17 Correct 1079 ms 120228 KB Output is correct
18 Correct 434 ms 111476 KB Output is correct
19 Correct 364 ms 108792 KB Output is correct
20 Correct 733 ms 116360 KB Output is correct