oj.uz

Submission #263380

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


	lis.reset();
	for (int range = 0; range < N; ++range) {
		for (int l = 1; l <= N - range; ++l) {
			lis.curVal = lis.maxVal = 0;
			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 47 ms 63352 KB Output is correct
2 Correct 47 ms 63360 KB Output is correct
3 Correct 54 ms 63352 KB Output is correct
4 Correct 48 ms 63456 KB Output is correct
5 Correct 48 ms 63480 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63352 KB Output is correct
2 Correct 47 ms 63360 KB Output is correct
3 Correct 54 ms 63352 KB Output is correct
4 Correct 48 ms 63456 KB Output is correct
5 Correct 48 ms 63480 KB Output is correct
6 Correct 48 ms 63480 KB Output is correct
7 Correct 47 ms 63352 KB Output is correct
8 Correct 48 ms 63352 KB Output is correct
9 Correct 48 ms 63352 KB Output is correct
10 Correct 50 ms 63480 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63352 KB Output is correct
2 Correct 47 ms 63360 KB Output is correct
3 Correct 54 ms 63352 KB Output is correct
4 Correct 48 ms 63456 KB Output is correct
5 Correct 48 ms 63480 KB Output is correct
6 Correct 48 ms 63480 KB Output is correct
7 Correct 47 ms 63352 KB Output is correct
8 Correct 48 ms 63352 KB Output is correct
9 Correct 48 ms 63352 KB Output is correct
10 Correct 50 ms 63480 KB Output is correct
11 Correct 172 ms 92800 KB Output is correct
12 Correct 52 ms 64124 KB Output is correct
13 Correct 71 ms 80404 KB Output is correct
14 Correct 332 ms 93776 KB Output is correct
15 Correct 121 ms 91128 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63352 KB Output is correct
2 Correct 47 ms 63360 KB Output is correct
3 Correct 54 ms 63352 KB Output is correct
4 Correct 48 ms 63456 KB Output is correct
5 Correct 48 ms 63480 KB Output is correct
6 Correct 48 ms 63480 KB Output is correct
7 Correct 47 ms 63352 KB Output is correct
8 Correct 48 ms 63352 KB Output is correct
9 Correct 48 ms 63352 KB Output is correct
10 Correct 50 ms 63480 KB Output is correct
11 Correct 172 ms 92800 KB Output is correct
12 Correct 52 ms 64124 KB Output is correct
13 Correct 71 ms 80404 KB Output is correct
14 Correct 332 ms 93776 KB Output is correct
15 Correct 121 ms 91128 KB Output is correct
16 Correct 127 ms 108536 KB Output is correct
17 Correct 851 ms 120056 KB Output is correct
18 Correct 200 ms 111092 KB Output is correct
19 Correct 134 ms 108536 KB Output is correct
20 Correct 513 ms 116084 KB Output is correct