#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };
int H, W;
int C[1002][1002] = {};
int Q;
int Y[1000000], X[1000000];
queue<pair<int,int>> que;
void fill2(int i, int j, int dy, int dx){
if(i < 0 || H+2 <= i || j < 0 || W+2 <= j) return;
if(C[i][j] == 2) return;
C[i][j] = 2;
fill2(i+dy, j+dx, dy, dx);
if(C[i+1][j-1] == 1) que.push({i+1, j-1});
}
void fill3(int i, int j, int dy, int dx){
if(i < 0 || H+2 <= i || j < 0 || W+2 <= j) return;
if(C[i][j] == 3) return;
C[i][j] = 3;
fill3(i+dy, j+dx, dy, dx);
if(C[i-1][j+1] == 1) que.push({i-1, j+1});
}
bool solved[1002][1002] = {};
void solve(){
while(!que.empty()){
int i = que.front().first;
int j = que.front().second;
que.pop();
if(solved[i][j]) continue;
if(C[i-1][j+1] == 2 && C[i+1][j-1] == 3) return;
C[i][j] = 1;
if(C[i-1][j+1] == 2){
fill2(i, j, -1, 0);
C[i][j] = 1;
fill2(i, j, 0, 1);
solved[i][j] = true;
}
if(C[i+1][j-1] == 3){
fill3(i, j, 1, 0);
C[i][j] = 1;
fill3(i, j, 0, -1);
solved[i][j] = true;
}
}
}
void print(){
/*for(int i=0; i<H+2; i++){
for(int j=0; j<W+2; j++){
printf("%d", C[i][j]);
}
printf("\n");
}*/
}
signed main(){
scanf("%d%d", &H, &W);
rep(i, H){
rep(j, W){
scanf("%d", &C[i+1][j+1]);
}
}
scanf("%d", &Q);
rep(i, Q){
scanf("%d%d", &Y[i], &X[i]);
}
for(int j=2; j<W+2; j++) C[0][j] = 2;
for(int i=0; i<H; i++) C[i][W+1] = 2;
for(int j=0; j<W; j++) C[H+1][j] = 3;
for(int i=2; i<H+2; i++) C[i][0] = 3;
print();
for(int i=1; i<H+1; i++){
for(int j=1; j<W+1; j++){
if(C[i][j] == 1){
que.push({i,j});
}
}
}
solve();
print();
rep(i, Q){
que.push({Y[i],X[i]});
solve();
printf("%d\n", C[Y[i]][X[i]] != 0);
}
print();
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
furniture.cpp:76:5: note: in expansion of macro 'rep'
76 | rep(i, H){
| ^~~
furniture.cpp:14:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
furniture.cpp:77:9: note: in expansion of macro 'rep'
77 | rep(j, W){
| ^~~
furniture.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
furniture.cpp:82:5: note: in expansion of macro 'rep'
82 | rep(i, Q){
| ^~~
furniture.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
furniture.cpp:102:5: note: in expansion of macro 'rep'
102 | rep(i, Q){
| ^~~
furniture.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | scanf("%d%d", &H, &W);
| ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
78 | scanf("%d", &C[i+1][j+1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
furniture.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
81 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
furniture.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf("%d%d", &Y[i], &X[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
768 KB |
Output is correct |
| 2 |
Correct |
2 ms |
896 KB |
Output is correct |
| 3 |
Correct |
3 ms |
896 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1024 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
768 KB |
Output is correct |
| 2 |
Correct |
2 ms |
896 KB |
Output is correct |
| 3 |
Correct |
3 ms |
896 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1024 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 10 |
Correct |
15 ms |
1280 KB |
Output is correct |
| 11 |
Correct |
4 ms |
768 KB |
Output is correct |
| 12 |
Correct |
236 ms |
12664 KB |
Output is correct |
| 13 |
Correct |
105 ms |
7928 KB |
Output is correct |
| 14 |
Correct |
432 ms |
20968 KB |
Output is correct |
| 15 |
Correct |
446 ms |
21372 KB |
Output is correct |
| 16 |
Correct |
510 ms |
23084 KB |
Output is correct |
| 17 |
Correct |
545 ms |
24184 KB |
Output is correct |
| 18 |
Correct |
498 ms |
23416 KB |
Output is correct |
| 19 |
Correct |
502 ms |
24700 KB |
Output is correct |
| 20 |
Correct |
445 ms |
24952 KB |
Output is correct |
| 21 |
Correct |
502 ms |
24952 KB |
Output is correct |
