oj.uz

Submission #374193

# Submission time Handle Problem Language Result Execution time Memory
374193 2021-03-06T21:11:53 Z ivan_tudor Furniture (JOI20_furniture) C++14
100 / 100
 305 ms 16976 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
bool good[N][N];
int mat[N][N];
int lft[2*N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool check(int i, int j){
  if(good[i-1][j] && good[i][j-1])
    return true;
  if(good[i + 1][j] && good[i][j + 1])
    return true;
  return false;
}
bool update(int i,int j){
  if(good[i][j] == true)
    return true;
  if(lft[i + j] == 1)
    return false;
  good[i][j] = true;
  lft[i + j]--;
  for(int k = 0; k <4;k++){
    int ni = i + dx[k];
    int nj = j + dy[k];
    if(good[ni][nj] == false && check(ni, nj)){
      update(ni, nj);
    }
  }
  return true;
}
int main()
{
  //freopen(".in","r",stdin);
  //freopen(".out", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, m;
  cin>>n>>m;
  for(int i = 1; i<=n;i++){
    for(int j =1 ; j<=m;j++){
      lft[i + j]++;
      cin>>mat[i][j];
    }
  }
  for(int i = 1; i<=n;i++)
    good[i][0] =  good[i][m + 1] = true;
  for(int i =1 ; i<=m;i++)
    good[0][i] = good[n + 1][i] = true;
  for(int i = 1; i<=n;i++){
    for(int j =1 ; j<=m;j++){
      if(mat[i][j])
        update(i, j);
    }
  }
  int q;
  cin>>q;
  for(int i=1;i<=q;i++){
    int x, y;
    cin>>x>>y;
    if(good[x][y] == true){
      cout<<"1\n";
      continue;
    }
    bool ans = update(x, y);
    cout<<ans<<"\n";
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 4 ms 1004 KB Output is correct
6 Correct 4 ms 1004 KB Output is correct
7 Correct 3 ms 1004 KB Output is correct
8 Correct 4 ms 1004 KB Output is correct
9 Correct 5 ms 1004 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 4 ms 1004 KB Output is correct
6 Correct 4 ms 1004 KB Output is correct
7 Correct 3 ms 1004 KB Output is correct
8 Correct 4 ms 1004 KB Output is correct
9 Correct 5 ms 1004 KB Output is correct
10 Correct 10 ms 1004 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 160 ms 10064 KB Output is correct
13 Correct 92 ms 7296 KB Output is correct
14 Correct 263 ms 14572 KB Output is correct
15 Correct 265 ms 14808 KB Output is correct
16 Correct 296 ms 15792 KB Output is correct
17 Correct 274 ms 16784 KB Output is correct
18 Correct 305 ms 16108 KB Output is correct
19 Correct 288 ms 16976 KB Output is correct
20 Correct 275 ms 16876 KB Output is correct
21 Correct 289 ms 16876 KB Output is correct