oj.uz

답안 #651114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
651114 2022-10-17T08:19:31 Z ymm Furniture (JOI20_furniture) C++17
100 / 100
 376 ms 15132 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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