oj.uz

Submission #293775

# Submission time Handle Problem Language Result Execution time Memory
293775 2020-09-08T11:56:23 Z BThero Furniture (JOI20_furniture) C++17
100 / 100
 3991 ms 7628 KB 
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)1e3 + 5;
const int MAXM = (int)1e6 + 9;

int dp[MAXN][MAXN];
char s[MAXN][MAXN];
int n, m, q;
vector<array<int, 3>> todo;

bool go(int diag, int l, int r) {
  if (l > r) {
    return 0;
  }

  if (diag == 0) {
    return 1;
  }
  
  todo.pb({diag, l, r});
  
  int nl = l, nr = r - 1;
  int x = l - 1, y = diag - l;
  
  if (x >= 0 && dp[x][y + 1] == 0) {
    nl--;
  }
  
  x = r, y = diag - r - 1;
  
  if (y >= 0 && dp[x + 1][y] == 0) {
    nr++;
  }
  
  return go(diag - 1, nl, nr);
}

void solve() {
  scanf("%d %d", &n, &m);
  
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      scanf(" %c", &s[i][j]);
    }
  }
  
  scanf("%d", &q);
  
  for (int x = n - 1; ~x; --x) {
    for (int y = m - 1; ~y; --y) {
      if (x == n - 1 && y == m - 1) {
        dp[x][y] = 1;
        continue;
      }
      
      dp[x][y] = 0;
    
      if (s[x][y] != '1') {
        dp[x][y] |= dp[x + 1][y];
        dp[x][y] |= dp[x][y + 1];
      }
    }
  }
  
  for (int i = 1; i <= q; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    
    if (dp[x][y] == 0) {
      s[x][y] = '1';
      printf("1\n");
      continue;
    }
    
    todo.clear();
    
    if (go(x + y, x, x)) {
      printf("0\n");
    }
    else {
      printf("1\n");
      s[x][y] = '1';
      
      for (auto &[diag, l, r] : todo) {
        for (int i = l; i <= r; ++i) {
          dp[i][diag - i] = 0;
        }
      }
    }
  }
}

int main() {
  int tt = 1;
  
  while (tt--) {
    solve();
  }

  return 0;
}

Compilation message

furniture.cpp: In function 'void solve()':
furniture.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:57:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |       scanf(" %c", &s[i][j]);
      |       ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
furniture.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 5 ms 896 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 26 ms 768 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 920 ms 6136 KB Output is correct
13 Correct 64 ms 5112 KB Output is correct
14 Correct 1957 ms 7032 KB Output is correct
15 Correct 1766 ms 7028 KB Output is correct
16 Correct 2119 ms 7096 KB Output is correct
17 Correct 452 ms 7544 KB Output is correct
18 Correct 3563 ms 7320 KB Output is correct
19 Correct 3991 ms 7544 KB Output is correct
20 Correct 948 ms 7544 KB Output is correct
21 Correct 1771 ms 7628 KB Output is correct