Submission #706460

#	Time	Username	Problem	Language	Result	Execution time	Memory
706460		600Mihnea	Robots (APIO13_robots)	C++17	100 / 100	1323 ms	114408 KiB

robots

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;

const int K = 10;
const int DIM = 500 + 7;
const int INF = (int)1e9 + 7;
const int dr[] = { -1, 0, 1, 0 };
const int dc[] = { 0, 1, 0, -1 };

int dp[DIM][DIM][K][K];
int k;
int cntrows;
int cntcols;
int a[DIM][DIM];
int adddir[DIM][DIM];
bool vis[DIM][DIM][4];
pair<int, int> w[DIM][DIM][4];

bool isvalid(int i, int j)
{
	return 1 <= i && i <= cntrows && 1 <= j && j <= cntcols;
}

pair<int, int> go(int r, int c, int k)
{
	int rn = r + dr[k];
	int cn = c + dc[k];
	if (!isvalid(rn, cn))
	{
		return { r, c };
	}
	if (a[rn][cn] == -1)
	{
		return { r, c };
	}
	r = rn;
	c = cn;
	k = (k + adddir[r][c]) % 4;
	return go(r, c, k);
}

struct T
{
	int i;
	int j;
	int st;
	int dr;
};

struct D
{
	int r;
	int c;
	int k;
};

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	cin >> k >> cntcols >> cntrows;
	
	for (int i = 1; i <= cntrows; i++)
	{
		string str;
		cin >> str;
		assert((int)str.size() == cntcols);
		for (int j = 1; j <= cntcols; j++)
		{
			char ch = str[j - 1];
			if ('1' <= ch && ch <= '9')
			{
				a[i][j] = ch - '0';
				assert(1 <= a[i][j] && a[i][j] <= 9);
				continue;
			}
			if (ch == '.')
			{
				a[i][j] = 0;
				continue;
			}
			if (ch == 'x')
			{
				a[i][j] = -1;
				continue;
			}
			a[i][j] = 0;
			assert(ch == 'A' || ch == 'C');
			if (ch == 'A')
			{
				adddir[i][j] = 3;
			}
			else
			{
				assert(ch == 'C');
				adddir[i][j] = 1;
			}
		}
	}
	{
		queue<D> q;
		for (int r = 1; r <= cntrows; r++)
		{
			for (int c = 1; c <= cntcols; c++)
			{
					if (a[r][c] == -1)
					{
						continue;
					}
				for (int k = 0; k < 4; k++)
				{
					int rn = r + dr[k];
					int cn = c + dc[k];
					if (!isvalid(rn, cn))
					{
						q.push({ r, c, k });
						w[r][c][k] = { r, c };
						vis[r][c][k] = 1;
						continue;
					}
					if (a[rn][cn] == -1)
					{
						q.push({ r, c, k });
						w[r][c][k] = { r, c };
						vis[r][c][k] = 1;
						continue;
					}
				}
			}
		}
		while (!q.empty())
		{
			auto it = q.front();
			q.pop();
			int r = it.r, c = it.c, k = it.k;
			//cout << " : " << r << " " << c << " " << k << "\n";
			auto now = w[r][c][k];
			k = (k + 4 - adddir[r][c]) % 4;
			r -= dr[k];
			c -= dc[k];
			if (isvalid(r, c) && a[r][c] != -1)
			{
				assert(!vis[r][c][k]);
				vis[r][c][k] = 1;
				q.push({ r, c, k });
				w[r][c][k] = now;
			}
		}
	}
	{
		for (int i = 1; i <= cntrows; i++)
		{
			for (int j = 1; j <= cntcols; j++)
			{
				if (a[i][j] == -1)
				{
					continue;
				}
				for (int k = 0; k < 4; k++)
				{
					assert(vis[i][j][k]);
				}
			}
		}
	}
	for (int i = 1; i <= cntrows; i++)
	{
		for (int j = 1; j <= cntcols; j++)
		{
			for (int l = 1; l <= k; l++)
			{
				for (int r = l; r <= k; r++)
				{
					dp[i][j][l][r] = INF;
				}
			}
			if (a[i][j] >= 1)
			{
				assert(1 <= a[i][j] && a[i][j] <= k);
				dp[i][j][a[i][j]][a[i][j]] = 0;
			}
		}
	}
	//{
	//	int r = 5, c = 5;
	//	cout << w[r][c][1].first << " " << w[r][c][1].second << "\n";
	//	exit(0);
	//}
	for (int len = 1; len <= k; len++)
	{
		for (int st = 1; st + len - 1 <= k; st++)
		{
			int dr = st + len - 1;
			for (int k = st; k < dr; k++)
			{
				for (int i = 1; i <= cntrows; i++)
				{
					for (int j = 1; j <= cntcols; j++)
					{
						dp[i][j][st][dr] = min(dp[i][j][st][dr], dp[i][j][st][k] + dp[i][j][k + 1][dr]);
					}
				}
			}
			vector<pair<int, T>> v;
			for (int i = 1; i <= cntrows; i++)
			{
				for (int j = 1; j <= cntcols; j++)
				{
					if (dp[i][j][st][dr] < INF)
					{
						v.push_back({ dp[i][j][st][dr], {i, j, st, dr} });
					}
				}
			}
			sort(v.begin(), v.end(), [&](pair<int, T> a, pair<int, T> b) {return a.first < b.first; });
			int pos = 0;
			vector<T> waiting;
			while (1)
			{
				queue<T> q;
				if (waiting.empty())
				{
					if (pos == (int)v.size())
					{
						break;
					}
					assert(pos < (int)v.size());
					int what = v[pos].first;
					while (pos < (int)v.size() && v[pos].first == what)
					{
						q.push(v[pos++].second);
					}
				}
				else
				{
					if (pos < (int)v.size())
					{
						auto& it = waiting[0];
						int what = dp[it.i][it.j][it.st][it.dr];
						assert(what <= v[pos].first);
						while (pos < (int)v.size() && v[pos].first == what)
						{
							q.push(v[pos++].second);
						}
					}
					else
					{
						assert(pos == (int)v.size());
					}
				}
				while (!waiting.empty())
				{
					q.push(waiting.back());
					waiting.pop_back();
				}

				while (!q.empty())
				{
					if (q.empty())
					{
						break;
					}
					auto it = q.front();
					q.pop();
					int i = it.i, j = it.j, st = it.st, dr = it.dr;
					for (int k = 0; k < 4; k++)
					{
						int in = w[i][j][k].first, jn = w[i][j][k].second;
						if (dp[i][j][st][dr] + 1 < dp[in][jn][st][dr])
						{
							dp[in][jn][st][dr] = 1 + dp[i][j][st][dr];
							waiting.push_back({ in, jn, st, dr });
						}
					}
				}
			}
		}
	}
	int sol = INF;
	for (int i = 1; i <= cntrows; i++)
	{
		for (int j = 1; j <= cntcols; j++)
		{
			sol = min(sol, dp[i][j][1][k]);
		}
	}
	if (sol == INF)
	{
		sol = -1;
	}
	cout << sol << "\n";
	return 0;
}

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