oj.uz

Submission #706460

# Submission time Handle Problem Language Result Execution time Memory
706460 2023-03-06T15:27:19 Z 600Mihnea Robots (APIO13_robots) C++17
100 / 100
 1323 ms 114408 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 256 ms 41948 KB Output is correct
12 Correct 22 ms 41296 KB Output is correct
13 Correct 110 ms 43168 KB Output is correct
14 Correct 411 ms 43752 KB Output is correct
15 Correct 215 ms 41500 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 256 ms 41948 KB Output is correct
12 Correct 22 ms 41296 KB Output is correct
13 Correct 110 ms 43168 KB Output is correct
14 Correct 411 ms 43752 KB Output is correct
15 Correct 215 ms 41500 KB Output is correct
16 Correct 519 ms 110184 KB Output is correct
17 Correct 1323 ms 114408 KB Output is correct
18 Correct 623 ms 110492 KB Output is correct
19 Correct 493 ms 112912 KB Output is correct
20 Correct 1040 ms 113408 KB Output is correct