oj.uz

답안 #263290

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
263290 2020-08-13T15:11:10 Z atoiz 로봇 (APIO13_robots) C++14
0 / 100
 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;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 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 -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 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 -