oj.uz

Submission #706449

# Submission time Handle Problem Language Result Execution time Memory
706449 2023-03-06T15:09:28 Z 600Mihnea Robots (APIO13_robots) C++17
60 / 100
 1500 ms 119120 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];
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 372 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 456 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 372 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 853 ms 45136 KB Output is correct
12 Correct 33 ms 43248 KB Output is correct
13 Correct 508 ms 45908 KB Output is correct
14 Correct 1274 ms 45752 KB Output is correct
15 Correct 724 ms 45180 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 372 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 853 ms 45136 KB Output is correct
12 Correct 33 ms 43248 KB Output is correct
13 Correct 508 ms 45908 KB Output is correct
14 Correct 1274 ms 45752 KB Output is correct
15 Correct 724 ms 45180 KB Output is correct
16 Execution timed out 1563 ms 119120 KB Time limit exceeded
17 Halted 0 ms 0 KB -