Submission #495941

#	Time	Username	Problem	Language	Result	Execution time	Memory
495941		minhcool	Furniture (JOI20_furniture)	C++17	0 / 100	6 ms	2696 KiB

furniture

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e3 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, m, c[N][N];
set<int> avail[N << 1];// diagonals

void prep(){
	avail[n + m].insert(n);
	for(int i = n + m - 1; i >= 2; i--){
		for(int x = max(1LL, i - m); x <= min(i - 1, n); x++){
			int y = i - x;
			if(c[x][y] == 1) continue;
			if(avail[i + 1].find(x) != avail[i + 1].end() || avail[i + 1].find(x + 1) != avail[i + 1].end()) avail[i].insert(x);
		}
	}
	assert(avail[2].size() != 0);
}

set<int> er[N << 1];

bool upd(int x, int y){
	if(avail[x + y].find(x) == avail[x + y].end()){
		c[x][y] = 1;
		return 1;
	}
	if(avail[x + y].size() == 1) return 0;
	er[x + y].clear();
	er[x + y].insert(x);
	for(int i = x + y; i >= 3; i--){
		if(!er[i].size()) break;
		er[i - 1].clear();
		for(auto tempx : er[i]){
			int tempy = i - tempx;
			// check {tempx - 1, tempy}  
			if(er[i].find(x - 1) != er[i].end() || avail[i].find(x - 1) == avail[i].end()) er[i - 1].insert(tempx - 1);
			// check {tempx, tempy - 1}
			if(er[i].find(x + 1) != er[i].end() || avail[i].find(x + 1) == avail[i].end()) er[i - 1].insert(tempx);
		}
	}
	for(int i = x + y; i >= 2; i--){
		if(!er[i].size()) break;
		for(auto it : er[i]) avail[i].erase(it);
	}
	assert(avail[2].size());
	c[x][y] = 1;
	return 1;
}

void process(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++) cin >> c[i][j];
	}
	prep();
	int q;
	cin >> q;
	while(q--){
		int x, y;
		cin >> x >> y;
		cout << upd(x, y) << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Compilation message (stderr)

furniture.cpp: In function 'bool upd(long long int, long long int)':
furniture.cpp:49:8: warning: unused variable 'tempy' [-Wunused-variable]
   49 |    int tempy = i - tempx;
      |        ^~~~~

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