답안 #583188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583188	2022-06-25T03:08:42 Z	penguinhacker	Furniture (JOI20_furniture)	C++17	100 / 100	281 ms	17900 KB

furniture

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

#define ll long long
#define ar array

const int mxN=1000;
int n, m, q, c[mxN][mxN], cnt[2*mxN];
bool can[2*mxN][mxN][2];

void dfs(int i, int j, bool t) {
	can[i][j][t]=1;
	if (t==0) {
		if (i+1<n&&!c[i+1][j]&&!can[i+1][j][0]) dfs(i+1, j, 0);
		if (j+1<m&&!c[i][j+1]&&!can[i][j+1][0]) dfs(i, j+1, 0);
	} else {
		if (i&&!c[i-1][j]&&!can[i-1][j][1]) dfs(i-1, j, 1);
		if (j&&!c[i][j-1]&&!can[i][j-1][1]) dfs(i, j-1, 1);
	}
}

void rem(int i, int j, bool t) {
	cnt[i+j]-=can[i][j][0]&&can[i][j][1];
	can[i][j][t]=0;
	if (t==0) {
		if (i+1<n&&can[i+1][j][0]&&(j==0||!can[i+1][j-1][0])) rem(i+1, j, 0);
		if (j+1<m&&can[i][j+1][0]&&(i==0||!can[i-1][j+1][0])) rem(i, j+1, 0);
	} else {
		if (i&&can[i-1][j][1]&&(j==m-1||!can[i-1][j+1][1])) rem(i-1, j, 1);
		if (j&&can[i][j-1][1]&&(i==n-1||!can[i+1][j-1][1])) rem(i, j-1, 1);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<n; ++i)
		for (int j=0; j<m; ++j)
			cin >> c[i][j];
	dfs(0, 0, 0);
	dfs(n-1, m-1, 1);
	for (int i=0; i<n; ++i)
		for (int j=0; j<m; ++j)
			if (can[i][j][0]&&can[i][j][1])
				++cnt[i+j];
	cin >> q;
	while(q--) {
		int i, j;
		cin >> i >> j, --i, --j;
		if (cnt[i+j]>1||!can[i][j][0]||!can[i][j][1]) {
			cout << "1\n";
			if (can[i][j][0]&&can[i][j][1]) {
				rem(i, j, 0);
				rem(i, j, 1);
			}
		} else
			cout << "0\n";
	}
	return 0;
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	724 KB	Output is correct
2	Correct	2 ms	852 KB	Output is correct
3	Correct	2 ms	808 KB	Output is correct
4	Correct	4 ms	856 KB	Output is correct
5	Correct	3 ms	980 KB	Output is correct
6	Correct	3 ms	980 KB	Output is correct
7	Correct	3 ms	980 KB	Output is correct
8	Correct	3 ms	980 KB	Output is correct
9	Correct	3 ms	980 KB	Output is correct

Subtask #2

95.0 / 95.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	724 KB	Output is correct
2	Correct	2 ms	852 KB	Output is correct
3	Correct	2 ms	808 KB	Output is correct
4	Correct	4 ms	856 KB	Output is correct
5	Correct	3 ms	980 KB	Output is correct
6	Correct	3 ms	980 KB	Output is correct
7	Correct	3 ms	980 KB	Output is correct
8	Correct	3 ms	980 KB	Output is correct
9	Correct	3 ms	980 KB	Output is correct
10	Correct	8 ms	1088 KB	Output is correct
11	Correct	3 ms	596 KB	Output is correct
12	Correct	136 ms	10728 KB	Output is correct
13	Correct	73 ms	7760 KB	Output is correct
14	Correct	250 ms	15220 KB	Output is correct
15	Correct	281 ms	15488 KB	Output is correct
16	Correct	261 ms	16456 KB	Output is correct
17	Correct	233 ms	17340 KB	Output is correct
18	Correct	227 ms	16840 KB	Output is correct
19	Correct	246 ms	17868 KB	Output is correct
20	Correct	228 ms	17696 KB	Output is correct
21	Correct	270 ms	17900 KB	Output is correct