oj.uz

Submission #249726

# Submission time Handle Problem Language Result Execution time Memory
249726 2020-07-15T15:42:03 Z DrumpfTheGodEmperor Robots (APIO13_robots) C++14
60 / 100
 1500 ms 121604 KB 
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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];
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]);
	}
	//Now do some shitty ass BFS.
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	fw (i, 0, n * m) if (dp[i][l][r] != inf) pq.push(ii(dp[i][l][r], i));
	while (!pq.empty()) {
		ii tmp = pq.top(); pq.pop();
		int u = tmp.se;
		if (tmp.fi != dp[u][l][r]) continue;
		fa (v, g[u]) if (dp[u][l][r] + 1 < dp[v][l][r]) {
			dp[v][l][r] = dp[u][l][r] + 1;
			pq.push(ii(dp[v][l][r], 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;
}

Compilation message

robots.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
robots.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 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 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 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 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 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 282 ms 48264 KB Output is correct
12 Correct 40 ms 47864 KB Output is correct
13 Correct 107 ms 48636 KB Output is correct
14 Correct 747 ms 48892 KB Output is correct
15 Correct 192 ms 48092 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 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 282 ms 48264 KB Output is correct
12 Correct 40 ms 47864 KB Output is correct
13 Correct 107 ms 48636 KB Output is correct
14 Correct 747 ms 48892 KB Output is correct
15 Correct 192 ms 48092 KB Output is correct
16 Correct 387 ms 120568 KB Output is correct
17 Execution timed out 1598 ms 121604 KB Time limit exceeded
18 Halted 0 ms 0 KB -