제출 #249726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
249726		DrumpfTheGodEmperor	로봇 (APIO13_robots)	C++14	60 / 100	1598 ms	121604 KiB

robots

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40