oj.uz

Submission #706450

# Submission time Handle Problem Language Result Execution time Memory
706450 2023-03-06T15:10:17 Z 600Mihnea Robots (APIO13_robots) C++17
60 / 100
 1500 ms 108904 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;
};


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 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 252 ms 41724 KB Output is correct
12 Correct 22 ms 40492 KB Output is correct
13 Correct 264 ms 41404 KB Output is correct
14 Correct 442 ms 43444 KB Output is correct
15 Correct 219 ms 41240 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 252 ms 41724 KB Output is correct
12 Correct 22 ms 40492 KB Output is correct
13 Correct 264 ms 41404 KB Output is correct
14 Correct 442 ms 43444 KB Output is correct
15 Correct 219 ms 41240 KB Output is correct
16 Execution timed out 1534 ms 108904 KB Time limit exceeded
17 Halted 0 ms 0 KB -