Submission #1159124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159124		Der_Vlapos	Furniture (JOI20_furniture)	C++20	0 / 100	4 ms	1092 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()

// #define int ll

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;

int dp1[1003][1003];
int dp2[1003][1003];

struct test
{
	void solve()
	{
		int n, m;
		cin >> n >> m;

		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j)
				cin >> dp1[i][j];

		dp2[n - 1][m - 1] = 1;

		for (int i = n - 1; i >= 0; --i)
			for (int j = m - 1 - (i == n - 1); j >= 0; --j)
				if (!dp1[i][j])
					dp2[i][j] = max(dp2[i + 1][j], dp2[i][j + 1]);

		dp1[0][0] = 1;
		for (int i = 0; i < n; ++i)
			for (int j = (i == 0); j < m; ++j)
				if (!dp1[i][j])
					dp1[i][j] = max((i ? dp1[i - 1][j] : 0), (j ? dp1[i][j - 1] : 0));
				else
					dp1[i][j] = 0;

		vector<vector<int>> good(n, vector<int>(m));
		vector<int> cntG(n + m + 1);
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j)
			{
				good[i][j] = (dp1[i][j] and dp2[i][j]);
				cntG[i + j] += good[i][j];
			}

		int q;
		cin >> q;
		queue<pii> bfs;

		vector<int> dx4 = {-1, -1, 1, 1};
		vector<int> dy4 = {-1, 1, -1, 1};

		auto isG = [&](int x, int y) -> bool
		{
			return x >= 0 and y >= 0 and x < n and y < m;
		};

		for (int i = 0; i < n + m - 1; ++i)
			assert(cntG[i]);

		for (int i = 0; i < q; ++i)
		{
			{
				int x, y;
				cin >> x >> y;
				--x, --y;
				if (!good[x][y])
				{
					cout << "1\n";
				}
				else if (cntG[x + y] == 1)
				{
					cout << "0\n";
				}
				else
				{
					cout << "1\n";
					good[x][y] = 0;
					bfs.push({x, y});
				}
			}
			while (bfs.size())
			{
				auto [x, y] = bfs.front();
				bfs.pop();
				cntG[x + y]--;
				// assert(cntG[x + y]);4

				for (int d = 0; d < 4; ++d)
				{
					int tox = x + dx4[d];
					int toy = y + dy4[d];
					if (isG(tox, toy) and !good[tox][toy])
					{
						if (good[x][toy])
						{
							good[x][toy] = 0;
							bfs.push({x, toy});
						}
						if (good[tox][y])
						{
							good[tox][y] = 0;
							bfs.push({tox, y});
						}
					}
				}
			}
		}
	}
};

main()
{
	test t;
	t.solve();
}

Compilation message (stderr)

furniture.cpp:121:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main()
      | ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95