Submission #374193

#TimeUsernameProblemLanguageResultExecution timeMemory
374193ivan_tudorFurniture (JOI20_furniture)C++14
100 / 100
305 ms16976 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...