oj.uz

답안 #378376

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
378376 2021-03-16T15:23:49 Z qwerty234 Furniture (JOI20_furniture) C++14
100 / 100
 670 ms 27780 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back

using namespace std;

const int MAXN = 1e3 + 10, inf = 2e9;

int n, m, q, a[MAXN][MAXN], b[MAXN][MAXN], c[MAXN][MAXN], dia[MAXN][MAXN], cnt[2 * MAXN];

void dfs1(int i, int j) {
  if (i < 1 || n < i || j < 1 || m < j || b[i][j] == 0)
    return;
  b[i][j] = (b[i - 1][j] | b[i][j - 1]);
  if (b[i][j] == 0) cnt[dia[i][j]] -= (b[i][j] | c[i][j]), dfs1(i + 1, j), dfs1(i, j + 1);
}

void dfs2(int i, int j) {
  if (i < 1 || n < i || j < 1 || m < j || c[i][j] == 0)
    return;
  c[i][j] = (c[i + 1][j] | c[i][j + 1]);
  if (c[i][j] == 0) cnt[dia[i][j]] -= (b[i][j] | c[i][j]), dfs2(i - 1, j), dfs2(i, j - 1);
}

void add(int i, int j) {
  cnt[dia[i][j]] -= (b[i][j] & c[i][j]);
  b[i][j] = c[i][j] = 0;
  dfs1(i + 1, j); dfs1(i, j + 1);
  dfs2(i - 1, j); dfs2(i, j - 1);
}

void precalc() {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      b[i][j] = c[i][j] = 1;
  int cur = 0;
  for (int j = 1; j <= m; j++) {
    cur++; int ci = 1, cj = j;
    while (ci <= n && cj >= 1) {
      dia[ci][cj] = cur; cnt[cur]++;
      ci++; cj--;
    }
  }
  for (int i = 2; i <= n; i++) {
    cur++; int ci = i, cj = m;
    while (ci <= n && cj >= 1) {
      dia[ci][cj] = cur; cnt[cur]++;
      ci++; cj--;
    }
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (a[i][j] == 1)
        add(i, j);
}

main() {
//  freopen("input.txt", "r", stdin);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      scanf("%d", &a[i][j]);
  scanf("%d", &q);
  precalc();
  while (q--) {
    int i, j;
    scanf("%d %d", &i, &j);
    int final = cnt[dia[i][j]] - (b[i][j] & c[i][j]);
    if (final == 0) {
      printf("0\n");
      continue;
    }
    add(i, j);
    printf("1\n");
  }
}

Compilation message

furniture.cpp:59:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main() {
      |      ^
furniture.cpp: In function 'int main()':
furniture.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:64:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |       scanf("%d", &a[i][j]);
      |       ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
furniture.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |     scanf("%d %d", &i, &j);
      |     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1516 KB Output is correct
2 Correct 3 ms 1900 KB Output is correct
3 Correct 3 ms 1900 KB Output is correct
4 Correct 5 ms 1900 KB Output is correct
5 Correct 5 ms 2028 KB Output is correct
6 Correct 5 ms 2028 KB Output is correct
7 Correct 6 ms 2028 KB Output is correct
8 Correct 5 ms 2028 KB Output is correct
9 Correct 5 ms 2028 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1516 KB Output is correct
2 Correct 3 ms 1900 KB Output is correct
3 Correct 3 ms 1900 KB Output is correct
4 Correct 5 ms 1900 KB Output is correct
5 Correct 5 ms 2028 KB Output is correct
6 Correct 5 ms 2028 KB Output is correct
7 Correct 6 ms 2028 KB Output is correct
8 Correct 5 ms 2028 KB Output is correct
9 Correct 5 ms 2028 KB Output is correct
10 Correct 15 ms 1644 KB Output is correct
11 Correct 4 ms 1260 KB Output is correct
12 Correct 335 ms 20716 KB Output is correct
13 Correct 120 ms 17388 KB Output is correct
14 Correct 584 ms 24844 KB Output is correct
15 Correct 604 ms 24916 KB Output is correct
16 Correct 624 ms 26092 KB Output is correct
17 Correct 670 ms 27428 KB Output is correct
18 Correct 579 ms 26604 KB Output is correct
19 Correct 612 ms 27780 KB Output is correct
20 Correct 461 ms 27748 KB Output is correct
21 Correct 588 ms 27772 KB Output is correct