Submission #651114

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
651114	2022-10-17T08:19:31 Z	ymm	Furniture (JOI20_furniture)	C++17	100 / 100	376 ms	15132 KB

furniture

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1024;
bool has_a[N][N], has_b[N][N], has_furn[N][N];
int n, m;

bool put_furn(int i, int j);

void expand(int i, int j, bool a[N][N])
{
	for (int x : {i-1, i, i+1}) for (int y : {j-1, j, j+1}) {
		if (x < 0 || n <= x || y < 0 || m <= y)
			continue;
		if (has_furn[x][y] && !a[x][y]) {
			a[x][y] = 1;
			put_furn(x, y);
		}
		a[x][y] = 1;
	}
}
	

bool put_furn(int i, int j)
{
	if (has_a[i][j] && has_b[i][j])
		return 0;
	has_furn[i][j] = 1;
	if (has_a[i][j]) {
		expand(i, j, has_a);
		LoopR (k,0,j) {
			if (has_furn[i][k])
				break;
			put_furn(i, k);
		}
		Loop (k,i+1,n) {
			if (has_furn[k][j])
				break;
			put_furn(k, j);
		}
	}
	if (has_b[i][j]) {
		expand(i, j, has_b);
		Loop (k,j+1,m) {
			if (has_furn[i][k])
				break;
			put_furn(i, k);
		}
		LoopR (k,0,i) {
			if (has_furn[k][j])
				break;
			put_furn(k, j);
		}
	}
	return 1;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,n) {
		has_a[i][0] = 1;
		has_b[i][m-1] = 1;
	}
	Loop (j,0,m) {
		has_a[n-1][j] = 1;
		has_b[0][j] = 1;
	}
	Loop (i,0,n) Loop (j,0,m) {
		int x;
		cin >> x;
		if (x)
			put_furn(i, j);
	}
	int q;
	cin >> q;
	while (q--) {
		int i, j;
		cin >> i >> j;
		cout << put_furn(i-1, j-1) << '\n';
	}
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	2 ms	596 KB	Output is correct
3	Correct	4 ms	592 KB	Output is correct
4	Correct	4 ms	724 KB	Output is correct
5	Correct	4 ms	720 KB	Output is correct
6	Correct	5 ms	724 KB	Output is correct
7	Correct	4 ms	724 KB	Output is correct
8	Correct	4 ms	724 KB	Output is correct
9	Correct	4 ms	724 KB	Output is correct

Subtask #2

95.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	2 ms	596 KB	Output is correct
3	Correct	4 ms	592 KB	Output is correct
4	Correct	4 ms	724 KB	Output is correct
5	Correct	4 ms	720 KB	Output is correct
6	Correct	5 ms	724 KB	Output is correct
7	Correct	4 ms	724 KB	Output is correct
8	Correct	4 ms	724 KB	Output is correct
9	Correct	4 ms	724 KB	Output is correct
10	Correct	11 ms	824 KB	Output is correct
11	Correct	3 ms	552 KB	Output is correct
12	Correct	185 ms	8456 KB	Output is correct
13	Correct	72 ms	5124 KB	Output is correct
14	Correct	301 ms	13048 KB	Output is correct
15	Correct	367 ms	13220 KB	Output is correct
16	Correct	329 ms	13844 KB	Output is correct
17	Correct	348 ms	14572 KB	Output is correct
18	Correct	376 ms	14892 KB	Output is correct
19	Correct	339 ms	15012 KB	Output is correct
20	Correct	307 ms	15132 KB	Output is correct
21	Correct	360 ms	15000 KB	Output is correct