oj.uz

답안 #249723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249723 2020-07-15T15:35:49 Z DrumpfTheGodEmperor 로봇 (APIO13_robots) C++14
60 / 100
 1500 ms 121764 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];
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;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 5 ms 6400 KB Output is correct
4 Correct 4 ms 6400 KB Output is correct
5 Correct 5 ms 6272 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 5 ms 6400 KB Output is correct
4 Correct 4 ms 6400 KB Output is correct
5 Correct 5 ms 6272 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 5 ms 6400 KB Output is correct
4 Correct 4 ms 6400 KB Output is correct
5 Correct 5 ms 6272 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 263 ms 48264 KB Output is correct
12 Correct 52 ms 47864 KB Output is correct
13 Correct 110 ms 48760 KB Output is correct
14 Correct 795 ms 48816 KB Output is correct
15 Correct 208 ms 48092 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 5 ms 6400 KB Output is correct
4 Correct 4 ms 6400 KB Output is correct
5 Correct 5 ms 6272 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 263 ms 48264 KB Output is correct
12 Correct 52 ms 47864 KB Output is correct
13 Correct 110 ms 48760 KB Output is correct
14 Correct 795 ms 48816 KB Output is correct
15 Correct 208 ms 48092 KB Output is correct
16 Correct 416 ms 120488 KB Output is correct
17 Execution timed out 1602 ms 121764 KB Time limit exceeded
18 Halted 0 ms 0 KB -