oj.uz

Submission #249852

# Submission time Handle Problem Language Result Execution time Memory
249852 2020-07-16T05:53:49 Z DrumpfTheGodEmperor Robots (APIO13_robots) C++14
60 / 100
 467 ms 163844 KB 
#include <bits/stdc++.h>
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 505, N2 = N * N;
typedef pair<int, int> ii;
int n, m, robots, dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; //x is the row, y is the column
char dName[] = {'N', 'E', 'S', 'W'};
char a[N][N];
ii enPos[N][N][4];
int getClockwise(int dir) {
	return (dir + 1) % 4;
}
int getAnti(int dir) {
	return (dir + 3) % 4;
}
bool check(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] != 'x') return true;
	return false;
}
ii getEnPos(int x, int y, int dir) {
	if (enPos[x][y][dir] != ii(-1, -1)) return enPos[x][y][dir];
	int ogDir = dir;
	
	if (a[x][y] == 'A') dir = getAnti(dir);
	if (a[x][y] == 'C') dir = getClockwise(dir);
	
	if (!check(x + dx[dir], y + dy[dir])) return enPos[x][y][ogDir] = ii(x, y);
	else return enPos[x][y][ogDir] = getEnPos(x + dx[dir], y + dy[dir], dir);
}
int getID(int x, int y) {
	return x * m + y;
}
int getID(ii a) {
	return a.fi * m + a.se;
}
vector<int> g[N2];
int dp[N2][10][10];
vector<int> sources[N2 * 10];
void solve(int l, int r) {
	fw (i, 0, n * m) {
		fw (mid, l, r) dp[i][l][r] = min(dp[i][l][r], dp[i][l][mid] + dp[i][mid + 1][r]);
		if (dp[i][l][r] < inf) sources[dp[i][l][r]].pb(i);
	}
	//Now do some shitty ass BFS.
	queue<int> q[2];
	//dp(i, l, r) <= n * m * (r - l + 1)
	fw (dist, 0, n * m * (r - l + 1) + 1) {
		fa (j, sources[dist]) if (dp[j][l][r] == dist) q[dist & 1].push(j);
		sources[dist].clear();
		while (!q[dist & 1].empty()) {
			int u = q[dist & 1].front(); q[dist & 1].pop();
			fa (v, g[u]) if (dp[u][l][r] + 1 < dp[v][l][r]) {
				dp[v][l][r] = dp[u][l][r] + 1;
				q[(dist + 1) & 1].push(v);
			}
		}
	}
//	fw (i, 0, n * m) if (dp[i][l][r] != inf) {
//		cout << "dp[" << i << "][" << l << "][" << r << "] = " << dp[i][l][r] << "\n";
//	}
}
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> robots >> m >> n;
	fw (i, 0, n) fw (j, 0, m) {
		cin >> a[i][j];
		fw (k, 0, 4) enPos[i][j][k] = ii(-1, -1);
	}
	
	fw (i, 0, n) fw (j, 0, m) {
		fw (dir, 0, 4) {
			ii enPos = getEnPos(i, j, dir);
			g[getID(i, j)].pb(getID(enPos));
		}
	}
	
	fw (i, 0, n * m) fw (l, 0, robots) fw (r, l, robots) dp[i][l][r] = inf;
	fw (i, 0, n) fw (j, 0, m) {
		if (a[i][j] >= '1' && a[i][j] <= '9') {
			int num = a[i][j] - '1';
//			cout << "num = " << num << " getID = " << getID(i, j) << "\n";
			dp[getID(i, j)][num][num] = 0;
		}
	} 
	
	fw (len, 1, robots + 1) {
		fw (l, 0, robots) {
			int r = l + len - 1;
			if (r >= robots) break;
			solve(l, r);
		}
	}
	int ans = inf;
	fw (i, 0, n * m) ans = min(ans, dp[i][0][robots - 1]);
	if (ans != inf) cout << ans; 
	else cout << "-1";
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 66304 KB Output is correct
2 Correct 38 ms 66168 KB Output is correct
3 Correct 39 ms 66304 KB Output is correct
4 Correct 40 ms 66424 KB Output is correct
5 Correct 43 ms 66296 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 66304 KB Output is correct
2 Correct 38 ms 66168 KB Output is correct
3 Correct 39 ms 66304 KB Output is correct
4 Correct 40 ms 66424 KB Output is correct
5 Correct 43 ms 66296 KB Output is correct
6 Correct 44 ms 66296 KB Output is correct
7 Correct 39 ms 66176 KB Output is correct
8 Correct 40 ms 66176 KB Output is correct
9 Correct 39 ms 66168 KB Output is correct
10 Correct 38 ms 66304 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 66304 KB Output is correct
2 Correct 38 ms 66168 KB Output is correct
3 Correct 39 ms 66304 KB Output is correct
4 Correct 40 ms 66424 KB Output is correct
5 Correct 43 ms 66296 KB Output is correct
6 Correct 44 ms 66296 KB Output is correct
7 Correct 39 ms 66176 KB Output is correct
8 Correct 40 ms 66176 KB Output is correct
9 Correct 39 ms 66168 KB Output is correct
10 Correct 38 ms 66304 KB Output is correct
11 Correct 343 ms 110072 KB Output is correct
12 Correct 77 ms 107580 KB Output is correct
13 Correct 184 ms 108408 KB Output is correct
14 Correct 467 ms 110892 KB Output is correct
15 Correct 288 ms 108408 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 66304 KB Output is correct
2 Correct 38 ms 66168 KB Output is correct
3 Correct 39 ms 66304 KB Output is correct
4 Correct 40 ms 66424 KB Output is correct
5 Correct 43 ms 66296 KB Output is correct
6 Correct 44 ms 66296 KB Output is correct
7 Correct 39 ms 66176 KB Output is correct
8 Correct 40 ms 66176 KB Output is correct
9 Correct 39 ms 66168 KB Output is correct
10 Correct 38 ms 66304 KB Output is correct
11 Correct 343 ms 110072 KB Output is correct
12 Correct 77 ms 107580 KB Output is correct
13 Correct 184 ms 108408 KB Output is correct
14 Correct 467 ms 110892 KB Output is correct
15 Correct 288 ms 108408 KB Output is correct
16 Runtime error 137 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -