Submission #354375

#	Time	Username	Problem	Language	Result	Execution time	Memory
354375		kuzma	Furniture (JOI20_furniture)	C++17	0 / 100	13 ms	8812 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;
vector<pii> pd;
int cnt  = 0;
int used[maxn][maxn];

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

int dfsd(int x, int y) {
	cnt++;
	used[x][y] = 1;
	pd.pb({x, y});
	if (x == n - 1 && y == m - 1)
		return 1;
	if (y + 1 < m && !a[x][y + 1] && !used[x][y + 1]) {
		if (dfsd(x, y + 1))
			return 1;
	}
	if (x + 1 < n && !a[x + 1][y] && !used[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];
		p[i + 1] = {x + 1, y};
		if (dfs2(i + 1))
			return 1;
		p[i + 1] = {t1, t2};
	}
	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];
		p[i + 1] = {x, y + 1};
		if (dfs2(i + 1))
			return 1;
		p[i + 1] = {t1, t2};
	}
	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';
	
	a[x][y] = 1;
	if (y + 1 < m && !a[x][y + 1]) {
		if (pd[i + 1] == make_pair(x, y + 1)) {
			a[x][y] = 0;
			return 1;
		}
		auto [t1, t2] = pd[i + 1];
		pd[i + 1] = {x, y + 1};
		if (dfs2d(i + 1)) {
			a[x][y] = 0;
 			return 1;
		}
		pd[i + 1] = {t1, t2};
	}
	if (x + 1 < n && !a[x + 1][y]) {
		if (pd[i + 1] == make_pair(x + 1, y)) {
			a[x][y] = 0;
			return 1;
		}
		auto [t1, t2] = pd[i + 1];
		pd[i + 1] = {x + 1, y};
		if (dfs2d(i + 1)) {
			a[x][y] = 0;
			return 1;
		}
		pd[i + 1] = {t1, t2};
	}
 	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);
	memset(used, 0, sizeof(used));
	dfsd(0, 0);
	int q;
	cin >> q;
	auto binu = [&] (int x, int y) {
		int l = 0, r = len;
		while (r - l > 1) {
			int mid = (l + r) / 2;
			if (make_pair(x, y) >= p[mid])
				l = mid;
			else
				r = mid;
		}
		return (p[l] == make_pair(x, y) ? l : 1e9);
	};
	auto bind = [&] (int x, int y) {
		int l = 0, r = len;
		while (r - l > 1) {
			int mid = (l + r) / 2;
			auto s = pd[mid];
			swap(s.f, s.s);
			if (make_pair(y, x) >= s)
				l = mid;
			else
				r = mid;
		}
		return (p[l] == make_pair(x, y) ? l : 1e9);
	};
	while (q--) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		int u = binu(x, y);
		int d = bind(x, y);
		if (u < len && d < len) {
			cout << 0 << "\n";
		} else {
			cout << 1 << '\n';
			if (u < len) {
				int j = u;
				a[x][y] = 1;
				j--;
				while (j >= 0 && !dfs2(j)) {
					j--;
				}
			} else if (d < len) {
				int j = d;
				a[x][y] = 1;
				j--;
				while (j >= 0 && !dfs2d(j)) {
					j--;
				}
			}
		}
		cout.flush();
	}
}

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;
}

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