oj.uz

답안 #354362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
354362 2021-01-21T19:34:58 Z kuzma Furniture (JOI20_furniture) C++17
0 / 100
 5000 ms 748 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 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];
		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);
	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--;
				}
			}
		}
	}
}

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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 620 KB Output is correct
2 Execution timed out 5068 ms 748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 620 KB Output is correct
2 Execution timed out 5068 ms 748 KB Time limit exceeded
3 Halted 0 ms 0 KB -