Submission #706449

#	Time	Username	Problem	Language	Result	Execution time	Memory
706449		600Mihnea	Robots (APIO13_robots)	C++17	60 / 100	1563 ms	119120 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];
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;
};

bool operator<(T a, T b)
{
	return 0;
}


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;
			}
		}
	}
	for (int i = 1; i <= cntrows; i++)
	{
		for (int j = 1; j <= cntcols; j++)
		{
			for (int k = 0; k < 4; k++)
			{
				w[i][j][k] = go(i, j, k);
			}
			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 st = k; st >= 1; st--)
	{
		for (int dr = st; dr <= k; dr++)
		{
			for (int mij = st; mij < dr; mij++)
			{
				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][mij] + dp[i][j][mij + 1][dr]);
					}
				}
			}
			priority_queue<pair<int, T>> pq;
			for (int i = 1; i <= cntrows; i++)
			{
				for (int j = 1; j <= cntcols; j++)
				{
					pq.push({ -dp[i][j][st][dr], {i, j, st, dr} });
				}
			}
			while (!pq.empty())
			{
				auto it = pq.top();
				pq.pop();
				it.first *= -1;
				int i = it.second.i;
				int j = it.second.j;
				int st = it.second.st;
				int dr = it.second.dr;
				if (dp[i][j][st][dr] != it.first)
				{
					continue;
				}
				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] = dp[i][j][st][dr] + 1;
						pq.push({ -dp[in][jn][st][dr], { in, jn, st, dr } });
					}
				}
			}
			continue;
			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: 0 / 40