Submission #263379

#	Time	Username	Problem	Language	Result	Execution time	Memory
263379		atoiz	Robots (APIO13_robots)	C++14	100 / 100	1079 ms	120228 KiB

robots

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40