oj.uz

Submission #869655

# Submission time Handle Problem Language Result Execution time Memory
869655 2023-11-05T08:06:45 Z rieyuw Spirale (COCI18_spirale) C++17
80 / 80
 41 ms 496 KB 
#include<bits/stdc++.h>

using namespace std;

#define sz(x) (int)(x).size()
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
const int mxN = 5e6 + 1;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m, k; cin >> n >> m >> k;

	int x[2][4] = {{-1, 0, 1, 0}, {-1, 0, 1, 0}};
	int y[2][4] = {{0, 1, 0, -1}, {0, -1, 0, 1}};

	vector<vector<long long>> grid(n, vector<long long>(m, (long long)1e18));

	while(k--)
	{
		long long r, c; cin >> r >> c; --r; --c;
		int t; cin >> t;

		int dir = 0, visited = 0, par = 0;
		long long time = 0, steps = 1, nxt = 2;

		auto move_spiral = [&](void) -> void
		{
			while (r >= 0 && r < n && c >= 0 && c < m)
			{
				grid[r][c] = min(grid[r][c], time);	 ++visited;
				long long nr = r + x[t][dir], nc = c + y[t][dir];
				if (steps > 0)
				{
					--steps; ++time;
					r = nr, c = nc;
				}
				if (steps == 0) break;
			} 
		};

		while(visited < n*m)
		{
			if (steps == 0)
			{
				if (par)
					steps = nxt++;
				else
					steps = nxt - 1;
				par ^= 1;
				dir = (dir == 3 ? 0 : dir + 1);
			}
			if (r >= 0 && r < n && c >= 0 && c < m)
			{
				move_spiral();
			}
			else
			{
				long long nr = r + steps*x[t][dir], nc = c + steps*y[t][dir], need;
				if (dir == 0) //UP
				{
					need = (r - (n - 1));
					if (r > (n-1) && steps >= need && nc >= 0 && nc < m)
					{
						steps -= need; time += need;
						r = (n-1);
						move_spiral();
					}
				}
				else if (dir == 2)//DOWN
				{
					need = (-r);
					if (r < 0 && steps >= need && nc >= 0 && nc < m)
					{
						steps -= need; time += need;
						r = 0;
						move_spiral();
					}
				}
				else //LEFT or RIGHT
				{
					if ((dir == 1) == t)//LEFT
					{
						need = (c - (m-1));
						if (c > (m - 1) && steps >= need && nr >= 0 && nr < n)
						{
							steps -= need; time += need;
							c = (m-1);
							move_spiral();
						}
					}
					else//RIGHT
					{
						need = (-c);
						if (c < 0 && steps >= need && nr >= 0 && nr < n)
						{
							steps -= need; time += need;
							c = 0;
							move_spiral();
						}
					}
				}
				need = abs(r - nr) + abs(c - nc);
				steps -= need; time += need;
				r = nr, c = nc;
			}
		}
	}

	for (int r = 0; r < n; ++r)
	{
		for (int c = 0; c < m; ++c)
			cout << grid[r][c] + 1 << " ";
		cout << "\n";
	}
}

Subtask #1
80.0 / 80.0

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