Submission #329111

#	Time	Username	Problem	Language	Result	Execution time	Memory
329111		terencehill	Furniture (JOI20_furniture)	C++14	0 / 100	4 ms	1900 KiB

furniture

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<int>> a;
vector<vector<vector<int>>> d, vis;

int addx[] = {1, 1, 1, 0, 0, -1, -1, -1};
int addy[] = {1, 0, -1, 1, -1, 1, -1, 0};

bool check(int i, int j, int c) {
	return (i < n && i >= 0 && j < m && j >= 0 && vis[i][j][c] != 1 && a[i][j] == 1);
}

bool check2(int i, int j, int c) {
	if(i < n && i >= 0 && j < m && j >= 0 && d[i][j][c] && a[i][j]) {
		return true;
	} else return false;
}

void bfs(int i, int j, int c) {
	if(check(i, j, c)) {
		d[i][j][c] = 1;
		vis[i][j][c] = 1;
		for(int k = 0; k < 8; k++) {
			bfs(i + addx[k], j + addy[k], c);
		}
	}
}

void solve() {
	cin >> n >> m;
	
	a.resize(n, vector<int>(m));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	
	d.resize(n, vector<vector<int>>(m, vector<int>(4, 0)));
	vis.resize(n, vector<vector<int>>(m, vector<int>(4, 0)));
	for(int i = 0; i < n; i++) bfs(i, 0, 0);
	for(int i = 0; i < n; i++) bfs(i, m - 1, 1);
	for(int i = 0; i < m; i++) bfs(0, i, 2);
	for(int i = 0; i < m; i++) bfs(n - 1, i, 3);
	
	int q;
	cin >> q;
	
	vis.clear();
	
	while(q--) {
		int i, j;
		cin >> i >> j;
		i--; j--;
		
//		for(int l = 0; l < n; l++) {
//			for(int z = 0; z < m; z++) {
//				cout << d[l][z][0] << " ";
//			}
//			cout << endl;
//		}
//		cout << endl;
//		for(int l = 0; l < n; l++) {
//			for(int z = 0; z < m; z++) {
//				cout << d[l][z][1] << " ";
//			}
//			cout << endl;
//		}
//		cout << endl;
//		for(int l = 0; l < n; l++) {
//			for(int z = 0; z < m; z++) {
//				cout << d[l][z][2] << " ";
//			}
//			cout << endl;
//		}
//		cout << endl;
//		for(int l = 0; l < n; l++) {
//			for(int z = 0; z < m; z++) {
//				cout << d[l][z][3] << " ";
//			}
//			cout << endl;
//		}
//		cout << endl;
		
		vector<int> tk(4, 0);
		for(int k = 0; k < 8; k++) {
			tk[0] |= check2(i + addx[k], j + addy[k], 0);
			tk[0] |= (j + addy[k] < 0);
			tk[1] |= check2(i + addx[k], j + addy[k], 1);
			tk[1] |= (j + addy[k] >= m);
			tk[2] |= check2(i + addx[k], j + addy[k], 2);
			tk[2] |= (i + addx[k] < 0);
			tk[3] |= check2(i + addx[k], j + addy[k], 3);
			tk[3] |= (i + addx[k] >= n);
		}
		
		if((tk[0] && tk[1]) || (tk[3] && tk[1]) || (tk[0] && tk[2]) || (tk[2] && tk[3])) {
			cout << 0 << endl;
		} else {
			cout << 1 << endl;
			a[i][j] = 1;
			
			if(tk[0]) bfs(i, j, 0);
			if(tk[1]) bfs(i, j, 1);
			if(tk[2]) bfs(i, j, 2);
			if(tk[3]) bfs(i, j, 3);
		}
	}
}

int main() {
	solve();
}

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