oj.uz

Submission #716294

# Submission time Handle Problem Language Result Execution time Memory
716294 2023-03-29T14:46:06 Z rainboy Furniture (JOI20_furniture) C
100 / 100
 393 ms 15860 KB 
#include <stdio.h>

#define N	1000
#define M	1000

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

int cc[N][M], kk[N + M], n, m;

void dfs(int i, int j) {
	int h, i_, j_, b;

	if (i == 0 && j == 0 || i == n - 1 && j == m - 1)
		return;
	b = 0;
	for (h = 0; h < 4; h++) {
		i_ = i + di[h], j_ = j + dj[h];
		if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] == 0)
			b |= 1 << h % 2;
	}
	if (b == 3)
		return;
	cc[i][j] = 1, kk[i + j]--;
	for (h = 0; h < 4; h++) {
		i_ = i + di[h], j_ = j + dj[h];
		if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] == 0)
			dfs(i_, j_);
	}
}

int main() {
	int q, h, i, j, i_, j_;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &cc[i][j]);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] == 0)
				kk[i + j]++;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] == 0)
				dfs(i, j);
	scanf("%d", &q);
	while (q--) {
		scanf("%d%d", &i, &j), i--, j--;
		if (cc[i][j]) {
			printf("1\n");
			continue;
		}
		if (kk[i + j] == 1)
			printf("0\n");
		else {
			printf("1\n");
			cc[i][j] = 1, kk[i + j]--;
			for (h = 0; h < 4; h++) {
				i_ = i + di[h], j_ = j + dj[h];
				if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] == 0)
					dfs(i_, j_);
			}
		}
	}
	return 0;
}

Compilation message

furniture.c: In function 'dfs':
furniture.c:14:13: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   14 |  if (i == 0 && j == 0 || i == n - 1 && j == m - 1)
      |      ~~~~~~~^~~~~~~~~
furniture.c: In function 'main':
furniture.c:35:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
furniture.c:38:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |    scanf("%d", &cc[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~
furniture.c:47:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
furniture.c:49:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

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 704 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 4 ms 740 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 704 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 4 ms 740 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 876 KB Output is correct
11 Correct 3 ms 552 KB Output is correct
12 Correct 270 ms 8780 KB Output is correct
13 Correct 98 ms 5900 KB Output is correct
14 Correct 339 ms 13364 KB Output is correct
15 Correct 319 ms 13768 KB Output is correct
16 Correct 384 ms 14560 KB Output is correct
17 Correct 390 ms 15396 KB Output is correct
18 Correct 338 ms 14996 KB Output is correct
19 Correct 393 ms 15744 KB Output is correct
20 Correct 363 ms 15860 KB Output is correct
21 Correct 373 ms 15780 KB Output is correct