Submission #541449

#	Time	Username	Problem	Language	Result	Execution time	Memory
541449		xuliu	Furniture (JOI20_furniture)	C++17	0 / 100	1 ms	340 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

/*

for every row i:
left[i] - position of last in prefix of row i that is disabled
right[i] - position of first in sufix of row i that is disabled
for every j > i : left[j] >= left[i]
for every j < i: right[j] <= right[i]

*/

const int N = 1e3 + 4;
int n, m;
int l[N], r[N];
bool used[N][N];

bool bad(int x, int y) {
	debug {
		if(x == 1 && y == 2) cerr<<"SPECIAL: l["<<x<<"] = "<<l[x]<<", r[x] = "<<r[x]<<"\n";
	}
	if(x <= 0 || x > n || y <= 0 || y > m) return 1;
	return l[x] >= y || y >= r[x];
}

void upd(int x, int y, bool print) {
	bool ok = 1, ind = 0, inu = 0;
	if(bad(x-1, y+1)) inu = 1;
	if(bad(x+1, y-1)) ind = 1;
	if(inu && ind) ok = 0;
	if(used[x][y]) ok = 0;
	debug cerr<<"for {"<<x<<", "<<y<<"}, inu = "<<inu<<" ; ind = "<<ind<<" ; so ok = "<<ok<<"\n";
	if(ok) {
		used[x][y] = 1;
		if(ind) {
			for(int i=x; i<=n; i++) {
				if(l[i] >= y) break;
				l[i] = y;
			}
		}
		if(inu) {
			for(int i=x; i>=1; i--) {
				if(r[i] <= y) break;
				r[i] = y;
			}
		}
	}
	if(print) cout<<ok<<"\n";
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; i++) r[i] = m+1;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			int c; cin>>c;
			if(c == 1) upd(i+1, j+1, 0);
		}
	}
	debug {
		for(int i=1; i<=n; i++) {
			cerr<<"l["<<i<<"] = "<<l[i]<<" ; r["<<i<<"] = "<<r[i]<<"\n";
		}
	}
	int q; cin>>q;
	while(q--) {
		int x, y; cin>>x>>y;
		upd(x, y, 1);
	}
}

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