Submission #869660

#	Time	Username	Problem	Language	Result	Execution time	Memory
869660		rieyuw	Spirale (COCI18_spirale)	C++17	80 / 80	50 ms	348 KiB

spirale

#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<int>> grid(n, vector<int>(m, INF));

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

		int dir = 0, visited = 0, par = 0;
		int 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;
				int 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
			{
				int 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 / 80