oj.uz

Submission #241301

# Submission time Handle Problem Language Result Execution time Memory
241301 2020-06-23T18:07:25 Z dolphingarlic Robots (APIO13_robots) C++14
60 / 100
 1500 ms 89224 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const int INF = 1061109567;

int n, h, w;
char g[500][500];
pair<int, int> end_pos[500][500][4];
int dp[500][500][9][9];

bool inside(int x, int y) {
	return (x >= 0 && y >= 0 && x < h && y < w && g[x][y] != 'x');
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> w >> h;
	memset(dp, 0x3f, sizeof(dp));

	FOR(i, 0, h) FOR(j, 0, w) {
		cin >> g[i][j];
		if (g[i][j] - '0' > 0 && g[i][j] - '0' < 10) {
			dp[i][j][g[i][j] - '1'][g[i][j] - '1'] = 0;
		}
	}

	// Determine final positions from each push
	FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
		FOR(k, 0, 4) {
			pair<int, int> pos = {i, j};
			int d = (k + (g[i][j] == 'A') * 3 + (g[i][j] == 'C')) % 4;  // NESW

			while (true) {
				if (d == 0) {
					if (inside(pos.first - 1, pos.second)) pos.first--;
					else break;
				} else if (d == 1) {
					if (inside(pos.first, pos.second + 1)) pos.second++;
					else break;
				} else if (d == 2) {
					if (inside(pos.first + 1, pos.second)) pos.first++;
					else break;
				} else {
					if (inside(pos.first, pos.second - 1)) pos.second--;
					else break;
				}

				if (g[pos.first][pos.second] == 'A') d = (d + 3) % 4;
				if (g[pos.first][pos.second] == 'C') d = (d + 1) % 4;
			}

			end_pos[i][j][k] = pos;
		}
	}

	// Find the minimum no. of pushes to get robot k-l to block (i, j)
	FOR(rng, 0, n) {
		FOR(k, 0, n - rng) {
			int l = k + rng;
			FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
				FOR(d, k, l) {
					dp[i][j][k][l] =
						min(dp[i][j][k][l],
							dp[i][j][k][d] + dp[i][j][d + 1][l]);
				}
			}
		}

		FOR(k, 0, n - rng) {
			int l = k + rng;
			priority_queue<pair<int, pair<int, int>>> pq;
			FOR(i, 0, h) FOR(j, 0, w) {
				if (dp[i][j][k][l] != INF && g[i][j] != 'x') {
					pq.push({-dp[i][j][k][l], {i, j}});
				}
			}
			while (pq.size()) {
				int x, y;
				tie(x, y) = pq.top().second;
				pq.pop();
				FOR(dir, 0, 4) {
					int nx, ny;
					tie(nx, ny) = end_pos[x][y][dir];
					if (dp[nx][ny][k][l] > dp[x][y][k][l] + 1) {
						dp[nx][ny][k][l] = dp[x][y][k][l] + 1;
						pq.push({-dp[nx][ny][k][l], {nx, ny}});
					}
				}
			}
		}
	}

	int ans = INT_MAX;
	FOR(i, 0, h) FOR(j, 0, w) ans = min(ans, dp[i][j][0][n - 1]);
	cout << (ans == INF ? -1 : ans);
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 79616 KB Output is correct
2 Correct 45 ms 79612 KB Output is correct
3 Correct 50 ms 79608 KB Output is correct
4 Correct 49 ms 79616 KB Output is correct
5 Correct 49 ms 79736 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 79616 KB Output is correct
2 Correct 45 ms 79612 KB Output is correct
3 Correct 50 ms 79608 KB Output is correct
4 Correct 49 ms 79616 KB Output is correct
5 Correct 49 ms 79736 KB Output is correct
6 Correct 46 ms 79608 KB Output is correct
7 Correct 47 ms 79608 KB Output is correct
8 Correct 45 ms 79608 KB Output is correct
9 Correct 45 ms 79608 KB Output is correct
10 Correct 49 ms 79608 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 79616 KB Output is correct
2 Correct 45 ms 79612 KB Output is correct
3 Correct 50 ms 79608 KB Output is correct
4 Correct 49 ms 79616 KB Output is correct
5 Correct 49 ms 79736 KB Output is correct
6 Correct 46 ms 79608 KB Output is correct
7 Correct 47 ms 79608 KB Output is correct
8 Correct 45 ms 79608 KB Output is correct
9 Correct 45 ms 79608 KB Output is correct
10 Correct 49 ms 79608 KB Output is correct
11 Correct 273 ms 83652 KB Output is correct
12 Correct 53 ms 82936 KB Output is correct
13 Correct 134 ms 83832 KB Output is correct
14 Correct 871 ms 84372 KB Output is correct
15 Correct 191 ms 83372 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 79616 KB Output is correct
2 Correct 45 ms 79612 KB Output is correct
3 Correct 50 ms 79608 KB Output is correct
4 Correct 49 ms 79616 KB Output is correct
5 Correct 49 ms 79736 KB Output is correct
6 Correct 46 ms 79608 KB Output is correct
7 Correct 47 ms 79608 KB Output is correct
8 Correct 45 ms 79608 KB Output is correct
9 Correct 45 ms 79608 KB Output is correct
10 Correct 49 ms 79608 KB Output is correct
11 Correct 273 ms 83652 KB Output is correct
12 Correct 53 ms 82936 KB Output is correct
13 Correct 134 ms 83832 KB Output is correct
14 Correct 871 ms 84372 KB Output is correct
15 Correct 191 ms 83372 KB Output is correct
16 Correct 603 ms 87672 KB Output is correct
17 Execution timed out 1595 ms 89224 KB Time limit exceeded
18 Halted 0 ms 0 KB -