Submission #354350

#	Time	Username	Problem	Language	Result	Execution time	Memory
354350		kuzma	Furniture (JOI20_furniture)	C++17	0 / 100	1 ms	748 KiB

furniture

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define int ll
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
using namespace std;
const int maxn = 1e3 + 10;
int a[maxn][maxn];
int n, m;

vector<pii> p;
map<pii, int> mp;
vector<pii> pd;
map<pii, int> mpd;

int dfs(int x, int y) {
	p.pb({x, y});
	if (x == n - 1 && y == m - 1)
		return 1;
	if (x + 1 < n && !a[x + 1][y]) {
		if (dfs(x + 1, y))
			return 1;
	}
	if (y + 1 < m && !a[x][y + 1]) {
		if (dfs(x, y + 1))
			return 1;
	}
	p.pop_back();
	return 0;
};

int dfsd(int x, int y) {
	pd.pb({x, y});
	if (x == n - 1 && y == m - 1)
		return 1;
	if (y + 1 < m && !a[x][y + 1]) {
		if (dfsd(x, y + 1))
			return 1;
	}
	if (x + 1 < n && !a[x + 1][y]) {
		if (dfsd(x + 1, y))
			return 1;
	}
	
	pd.pop_back();
	return 0;
};


int dfs2(int i) {
	auto [x, y] = p[i];
	if (x == n - 1 && y == m - 1)
		return 1;
	// cout << x << ' ' << y << '\n';
	if (x + 1 < n && !a[x + 1][y]) {
		if (p[i + 1] == make_pair(x + 1, y))
			return 1;
		auto [t1, t2] = p[i + 1];
		mp.erase(p[i + 1]);
		p[i + 1] = {x + 1, y};
		mp[p[i + 1]] = i + 1;
		if (dfs2(i + 1))
			return 1;
		mp.erase(p[i + 1]);
		p[i + 1] = {t1, t2};
		mp[p[i + 1]] = i + 1;
	}
	if (y + 1 < m && !a[x][y + 1]) {
		if (p[i + 1] == make_pair(x, y + 1))
			return 1;
		auto [t1, t2] = p[i + 1];
		mp.erase(p[i + 1]);
		p[i + 1] = {x, y + 1};
		mp[p[i + 1]] = i + 1;
		if (dfs2(i + 1))
			return 1;
		mp.erase(p[i + 1]);
		p[i + 1] = {t1, t2};
		mp[p[i + 1]] = i + 1;
	}
	a[x][y] = 1;
 	return 0;
}


int dfs2d(int i) {
	auto [x, y] = pd[i];
	if (x == n - 1 && y == m - 1)
		return 1;
	// cout << x << ' ' << y << '\n';
	if (x + 1 < n && !a[x + 1][y]) {
		if (pd[i + 1] == make_pair(x + 1, y))
			return 1;
		auto [t1, t2] = pd[i + 1];
		mpd.erase(pd[i + 1]);
		pd[i + 1] = {x + 1, y};
		mpd[pd[i + 1]] = i + 1;
		if (dfs2d(i + 1))
			return 1;
		mp.erase(pd[i + 1]);
		pd[i + 1] = {t1, t2};
		mpd[pd[i + 1]] = i + 1;
	}
	if (y + 1 < m && !a[x][y + 1]) {
		if (pd[i + 1] == make_pair(x, y + 1))
			return 1;
		auto [t1, t2] = pd[i + 1];
		mpd.erase(pd[i + 1]);
		pd[i + 1] = {x, y + 1};
		mpd[pd[i + 1]] = i + 1;
		if (dfs2d(i + 1))
			return 1;
		mpd.erase(pd[i + 1]);
		pd[i + 1] = {t1, t2};
		mpd[pd[i + 1]] = i + 1;
	}
	a[x][y] = 1;
 	return 0;
}

void solve() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> a[i][j];
	int len = n + m - 1;
	dfs(0, 0);
	for (int i = 0; i < len; ++i)
		mp[p[i]] = i;
	dfsd(0, 0);

	for (int i = 0; i < len; ++i)
		mpd[pd[i]] = i;
	int q;
	cin >> q;
	bool govno = 0;
	while (q--) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		if (mp.count({x, y}) && mpd.count({x, y})) {
			cout << 0 << "\n";
		} else {
			cout << 1 << '\n';
			if (mp.count({x, y})) {
				int j = mp[{x, y}];
				a[x][y] = 1;
				j--;
				while (j >= 0 && !dfs2(j)) {
					j--;
				}
			} else if (mpd.count({x, y})) {
				int j = mpd[{x, y}];
				a[x][y] = 1;
				j--;
				while (j >= 0 && !dfs2d(j)) {
					j--;
				}
			}
		}
	}
}

signed main() {
	#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	#endif // LOCAL
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.precision(10);
	int t = 1;
	// cin >> t;
	while (t--)
		solve();
	return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'void solve()':
furniture.cpp:140:7: warning: unused variable 'govno' [-Wunused-variable]
  140 |  bool govno = 0;
      |       ^~~~~

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