oj.uz

Submission #354387

# Submission time Handle Problem Language Result Execution time Memory
354387 2021-01-21T20:23:59 Z kuzma Furniture (JOI20_furniture) C++17
100 / 100
 2535 ms 28264 KB 
#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';
	
	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];
		pd[i + 1] = {x, y + 1};
		if (dfs2d(i + 1)) {
			return 1;
		}
		pd[i + 1] = {t1, t2};
	}
	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];
		pd[i + 1] = {x + 1, y};
		if (dfs2d(i + 1)) {
			return 1;
		}
		pd[i + 1] = {t1, t2};
	}
 	
	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);
	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 (pd[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);
		// cout << d << endl;
		for (int j = 0; j < len; ++j) {
			if (pd[j] == make_pair(x, y)) {
				d = j;
				break;
			}
		}
		// cout << u << ' ' << d << endl;
		// if (d < len) {
		// 	cout << x << ' ' << y << '\n';
		// 	for (auto &i : pd)
		// 		cout << i.f << ' ' << i.s << '\n';
		// 	cout << "123\n";
		// 	exit(0);
		// }
		if (u < len && d < len) {
			cout << 0 << "\n";
		} else {
			cout << 1 << '\n';
			a[x][y] = 1;
			if (u < len) {
				int j = u;
				j--;
				while (j >= 0 && !dfs2(j)) {
					j--;
				}
			} else if (d < len) {
				int j = d;
				j--;
				while (j >= 0 && !dfs2d(j)) {
					j--;
				}
			}
		}
	}
}

signed main() {
	// #ifdef LOCAL
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	// #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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8684 KB Output is correct
2 Correct 7 ms 8812 KB Output is correct
3 Correct 8 ms 8812 KB Output is correct
4 Correct 11 ms 8940 KB Output is correct
5 Correct 11 ms 8940 KB Output is correct
6 Correct 12 ms 8940 KB Output is correct
7 Correct 11 ms 8940 KB Output is correct
8 Correct 13 ms 8940 KB Output is correct
9 Correct 11 ms 9068 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8684 KB Output is correct
2 Correct 7 ms 8812 KB Output is correct
3 Correct 8 ms 8812 KB Output is correct
4 Correct 11 ms 8940 KB Output is correct
5 Correct 11 ms 8940 KB Output is correct
6 Correct 12 ms 8940 KB Output is correct
7 Correct 11 ms 8940 KB Output is correct
8 Correct 13 ms 8940 KB Output is correct
9 Correct 11 ms 9068 KB Output is correct
10 Correct 43 ms 9284 KB Output is correct
11 Correct 9 ms 8684 KB Output is correct
12 Correct 808 ms 20972 KB Output is correct
13 Correct 95 ms 17900 KB Output is correct
14 Correct 2003 ms 25708 KB Output is correct
15 Correct 2047 ms 25740 KB Output is correct
16 Correct 2290 ms 26736 KB Output is correct
17 Correct 2475 ms 27872 KB Output is correct
18 Correct 2351 ms 27116 KB Output is correct
19 Correct 2535 ms 28264 KB Output is correct
20 Correct 2383 ms 28208 KB Output is correct
21 Correct 2500 ms 28116 KB Output is correct