Submission #399898

#	Time	Username	Problem	Language	Result	Execution time	Memory
399898		nikatamliani	Furniture (JOI20_furniture)	C++14	0 / 100	3 ms	832 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
bool a[N][N], b[N][N];
int n, m, q, x[N], y[N], cnt[N][N];
bool check(int id, int banned_x = 0, int banned_y = 0) {
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			b[i][j] = a[i][j];
			cnt[i][j] = 0;
		}
	}
	for(int i = 1; i <= id; ++i) {
		b[x[i]][y[i]] = 1;
	}
	b[banned_x][banned_y] = 0;
	cnt[1][1] = 1;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(b[i][j] == 0) {
				cnt[i][j] += cnt[i-1][j];
				cnt[i][j] += cnt[i][j-1];
				cnt[i][j] = min(cnt[i][j], 2);
			}
		}
	}
	if(banned_x == 0) 
		return cnt[n][m] == 0;
	return cnt[n][m] < 2;
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			cin >> a[i][j];
		}
	}
	cin >> q;
	for(int i = 1; i <= q; ++i) {
		cin >> x[i] >> y[i];
	}
	int l = 1, r = q, pos1 = q+1, pos2 = q+1;
	while(r >= l) {
		int m = l + r >> 1;
		if(check(m)) {
			r = m - 1;
			pos1 = m;
		} else {
			l = m + 1;
		}
	}
	l = pos1, r = q;
	while(r >= l) {
		int m = l + r >> 1;
		if(check(m, x[pos1], y[pos1])) {
			r = m - 1;
			pos2 = m;
		} else {
			l = m + 1;
		}
	}
	check(pos2, x[pos1], y[pos1]);
	for(int i = 1; i <= q; ++i) {
		if(i < pos1) {
			cout << "1\n";
		} else if(i < pos2) {
			if(x[i] == x[pos1] && y[i] == y[pos1]) {
				cout << "0\n";
			} else {
				cout << "1\n";
			}
		} else {
			cout << (cnt[x[i]][y[i]] != 1) << '\n';
		}
	}
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int m = l + r >> 1;
      |           ~~^~~
furniture.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int m = l + r >> 1;
      |           ~~^~~

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