oj.uz

Submission #249863

# Submission time Handle Problem Language Result Execution time Memory
249863 2020-07-16T07:07:44 Z DrumpfTheGodEmperor Robots (APIO13_robots) C++14
100 / 100
 1215 ms 130184 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], og[N2], cnt[N2 * 10], per[N2];
void solve(int l, int r) {
	fw (i, 0, n * m * (r - l + 1) + 1) cnt[i] = 0;
	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]);
			og[i] = dp[i][l][r];
		}
		if (dp[i][l][r] != inf) cnt[dp[i][l][r]]++;
	}
	//Use counting sort to sort the dp(i, l, r), then pointer.
	fw (i, 1, n * m * (r - l + 1) + 1) cnt[i] += cnt[i - 1];
	int tot = 0;
	fw (i, 0, n * m) if (dp[i][l][r] != inf) {
		tot++;
		per[--cnt[dp[i][l][r]]] = i;
	}
	//Now do some shitty ass BFS.
	queue<int> q[2];
	//dp(i, l, r) <= n * m * (r - l + 1)
	int ptr = 0;
	fw (dist, 0, n * m * (r - l + 1) + 1) {
		while (ptr < tot && og[per[ptr]] == dist) {
			if (dp[per[ptr]][l][r] == dist) q[dist & 1].push(per[ptr]);
			ptr++;
		}
		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 4 ms 6400 KB Output is correct
2 Correct 4 ms 6400 KB Output is correct
3 Correct 3 ms 6400 KB Output is correct
4 Correct 4 ms 6400 KB Output is correct
5 Correct 4 ms 6400 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6400 KB Output is correct
2 Correct 4 ms 6400 KB Output is correct
3 Correct 3 ms 6400 KB Output is correct
4 Correct 4 ms 6400 KB Output is correct
5 Correct 4 ms 6400 KB Output is correct
6 Correct 4 ms 6400 KB Output is correct
7 Correct 4 ms 6400 KB Output is correct
8 Correct 4 ms 6400 KB Output is correct
9 Correct 4 ms 6400 KB Output is correct
10 Correct 4 ms 6400 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6400 KB Output is correct
2 Correct 4 ms 6400 KB Output is correct
3 Correct 3 ms 6400 KB Output is correct
4 Correct 4 ms 6400 KB Output is correct
5 Correct 4 ms 6400 KB Output is correct
6 Correct 4 ms 6400 KB Output is correct
7 Correct 4 ms 6400 KB Output is correct
8 Correct 4 ms 6400 KB Output is correct
9 Correct 4 ms 6400 KB Output is correct
10 Correct 4 ms 6400 KB Output is correct
11 Correct 292 ms 51324 KB Output is correct
12 Correct 43 ms 48120 KB Output is correct
13 Correct 179 ms 51380 KB Output is correct
14 Correct 397 ms 51320 KB Output is correct
15 Correct 271 ms 51320 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6400 KB Output is correct
2 Correct 4 ms 6400 KB Output is correct
3 Correct 3 ms 6400 KB Output is correct
4 Correct 4 ms 6400 KB Output is correct
5 Correct 4 ms 6400 KB Output is correct
6 Correct 4 ms 6400 KB Output is correct
7 Correct 4 ms 6400 KB Output is correct
8 Correct 4 ms 6400 KB Output is correct
9 Correct 4 ms 6400 KB Output is correct
10 Correct 4 ms 6400 KB Output is correct
11 Correct 292 ms 51324 KB Output is correct
12 Correct 43 ms 48120 KB Output is correct
13 Correct 179 ms 51380 KB Output is correct
14 Correct 397 ms 51320 KB Output is correct
15 Correct 271 ms 51320 KB Output is correct
16 Correct 767 ms 130184 KB Output is correct
17 Correct 1215 ms 129916 KB Output is correct
18 Correct 765 ms 129740 KB Output is correct
19 Correct 712 ms 130168 KB Output is correct
20 Correct 1002 ms 129792 KB Output is correct