Submission #500709

#	Time	Username	Problem	Language	Result	Execution time	Memory
500709		CodeTiger927	Robots (APIO13_robots)	C++14	100 / 100	434 ms	134180 KiB

robots

using namespace std;

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

#define MAXN 505
#define INF 1e6

int N,M,K,dp[9][9][MAXN][MAXN],mxn;
vector<pair<int,int>> dist[MAXN * MAXN];
pair<int,int> to[MAXN][MAXN][4];
char g[MAXN][MAXN];
bool vis[MAXN][MAXN],vis2[MAXN][MAXN];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
vector<pair<pair<int,int>,int>> order;

pair<int,int> dfs(int a,int b,int c) {
	if(to[a][b][c].first != 0) return to[a][b][c];
	to[a][b][c] = {a,b};
	if(a <= 0 || a > N || b <= 0 || b > M || g[a][b] == 'x') {
		return to[a][b][c] = {-1,-1};
	}else if(g[a][b] == '.') {
		to[a][b][c] = dfs(a + dx[c],b + dy[c],c);
	}else if(g[a][b] == 'C') {
		int uwu = (c + 1) % 4;
		to[a][b][c] = dfs(a + dx[uwu],b + dy[uwu],uwu);
	}else{
		int uwu = (c + 3) % 4;
		to[a][b][c] = dfs(a + dx[uwu],b + dy[uwu],uwu);
	}
	if(to[a][b][c].first == -1) to[a][b][c] = {a,b};
	order.push_back({{a,b},c});
	return to[a][b][c];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> K >> M >> N;
	memset(dp,-1,sizeof(dp));
	for(int i = 1;i <= N;++i) {
		for(int j = 1;j <= M;++j) {
			cin >> g[i][j];
			if(g[i][j] - '1' < K && g[i][j] - '1' >= 0) {
				int uwu = g[i][j] - '1';
				dp[uwu][uwu][i][j] = 0;
				// cout << uwu << " " << i << " " << j << endl;
				g[i][j] = '.';
				vis[i][j] = true;
			}
		}
	}
	for(int i = 1;i <= N;++i) {
		for(int j = 1;j <= M;++j) {
			for(int k = 0;k < 4;++k) {
				dfs(i,j,k);
			}
		}
	}
	reverse(order.begin(),order.end());
	for(int k = 0;k < K;++k) {
		for(int i = 0;i < K - k;++i) {
			// cout << dp[0][1][1][1] << endl;
			int j = i + k;
			// cout << i << " " << j << endl;
			mxn = 0;
			for(int a = 1;a <= N;++a) {
				for(int b = 1;b <= M;++b) {
					// cout << a << " " << b << endl;
					if(dp[i][j][a][b] == -1) dp[i][j][a][b] = INF;
					if(g[a][b] == 'x' || !vis[a][b]) continue;
					for(int l = i;l < j;++l) {
						dp[i][j][a][b] = min(dp[i][j][a][b],dp[i][l][a][b] + dp[l + 1][j][a][b]);
					}
					if(dp[i][j][a][b] < INF) {
						dist[dp[i][j][a][b]].push_back({a,b});
						mxn = max(mxn,dp[i][j][a][b]);
					}
					// if(dp[i][j][a][b] < INF) cout << dp[i][j][a][b] << endl;
				}
			}
			// cout << "DONE" << endl;
			memset(vis2,0,sizeof(vis2));
			for(int a = 0;a <= mxn;++a) {
				// cout << a << " " << mxn << endl;
				for(auto [x,y] : dist[a]) {
					if(vis2[x][y]) continue;
					vis2[x][y] = true;
					for(int b = 0;b < 4;++b) {
						int w = to[x][y][b].first;
						int z = to[x][y][b].second;
						// if(i == 1 && j == 1 && w == 2 && z == 1) cout << i << " " << j << " " << b << " " << x << " " << y << " " << w << " " << z << endl;
						// cout << x << " " << y << endl;
						// cout << b << endl;
						if(dp[i][j][x][y] + 1 < dp[i][j][w][z]) {
							dp[i][j][w][z] = dp[i][j][x][y] + 1;
							vis[w][z] = true;
							dist[dp[i][j][w][z]].push_back({w,z});
							mxn = max(mxn,dp[i][j][w][z]);
						}
					}
				}
				dist[a].clear();
			}
		}
	}
	int ans = INF;
	for(int i = 1;i <= N;++i) {
		for(int j = 1;j <= M;++j) {
			ans = min(ans,dp[0][K - 1][i][j]);
		}
	}
	// cout << to[4][1][3].first << " " << to[4][1][3].second << endl;
	// cout << dp[1][1][1][1] << endl;
	cout << (ans >= INF ? -1 : ans) << endl;
	return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:89:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |     for(auto [x,y] : dist[a]) {
      |              ^

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40