#include<bits/stdc++.h>
#define st first
#define nd second
#define eb emplace_back
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){cerr<<h;if(sizeof...(t))cerr<<", ";debug(t...);};
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1e3+5, INF=1e9+5;
bool czy[2][N][N], blo[N][N];
set<int> S[N], S2[N];
#define dobre(x, y) (czy[0][x][y]&czy[1][x][y])
void upd(int x, int y){
if(dobre(x, y))S[x].erase(y);
if(dobre(x, y))S2[y].erase(x);
czy[0][x][y]=(!blo[x][y])&(czy[0][x-1][y]|czy[0][x][y-1]);
czy[1][x][y]=(!blo[x][y])&(czy[1][x+1][y]|czy[1][x][y+1]);
if(dobre(x, y))S[x].insert(y);
if(dobre(x, y))S2[y].insert(x);
}
vector<pii> edg={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n, m;
cin>>n>>m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>blo[i][j];
}
}
czy[0][1][0]=1;
czy[1][n][m+1]=1;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
upd(i, j);
}
}
for(int i=n; i>0; i--){
for(int j=m; j>0; j--){
upd(i, j);
}
}
int q;
cin>>q;
while(q--){
int x, y;
cin>>x>>y;
/*for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cout<<dobre(i, j)<<" \n"[j==m];
}
}*/
if(!dobre(x, y)){
cout<<1<<"\n";
continue;
}
blo[x][y]=1;
upd(x, y);
vector<pii> todo;
todo.eb(x, y);
for(int i=x+1; i<=n; i++){
if(!dobre(i, y))break;
todo.eb(i, y);
upd(i, y);
if(dobre(i, y))break;
}
for(int i=x-1; i>=1; i--){
if(!dobre(i, y))break;
todo.eb(i, y);
upd(i, y);
if(dobre(x, y))break;
}
for(int i=y+1; i<=m; i++){
if(!dobre(x, i))break;
todo.eb(x, i);
upd(x, i);
if(dobre(x, i))break;
}
for(int i=y-1; i>=1; i--){
if(!dobre(x, i))break;
todo.eb(x, i);
upd(x, i);
if(dobre(x, i))break;
}
if(S[x].size() && S2[y].size()){
int mx=*S[x].begin(), Mx=*(--S[x].end());
int my=*S2[y].begin(), My=*(--S2[y].end());
//deb(mx, Mx,my,My);
if(!(mx>y && my>x) && !(Mx<y && My<x)){
cout<<1<<"\n";
for(int i=0; i<todo.size(); i++){
int xx=todo[i].st, yy=todo[i].nd;
for(pii e:edg){
int xxx=xx+e.st, yyy=yy+e.nd;
if(!(xxx%(n+1)) || !(yyy%(m+1)))continue;
int sta=czy[0][xxx][yyy]+2*czy[1][xxx][yyy];
upd(xxx, yyy);
sta-=czy[0][xxx][yyy]+2*czy[1][xxx][yyy];
if(sta){
todo.eb(xxx, yyy);
}
}
}
continue;
}
}
cout<<0<<"\n";
blo[x][y]=0;
for(pii i:todo)upd(i.st, i.nd);
}
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i=0; i<todo.size(); i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
3 ms |
852 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1188 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1336 KB |
Output is correct |
| 5 |
Correct |
15 ms |
1416 KB |
Output is correct |
| 6 |
Correct |
45 ms |
1688 KB |
Output is correct |
| 7 |
Correct |
17 ms |
1716 KB |
Output is correct |
| 8 |
Correct |
14 ms |
1688 KB |
Output is correct |
| 9 |
Correct |
10 ms |
1748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
3 ms |
852 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1188 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1336 KB |
Output is correct |
| 5 |
Correct |
15 ms |
1416 KB |
Output is correct |
| 6 |
Correct |
45 ms |
1688 KB |
Output is correct |
| 7 |
Correct |
17 ms |
1716 KB |
Output is correct |
| 8 |
Correct |
14 ms |
1688 KB |
Output is correct |
| 9 |
Correct |
10 ms |
1748 KB |
Output is correct |
| 10 |
Correct |
18 ms |
952 KB |
Output is correct |
| 11 |
Correct |
16 ms |
1284 KB |
Output is correct |
| 12 |
Correct |
3557 ms |
77092 KB |
Output is correct |
| 13 |
Correct |
585 ms |
53624 KB |
Output is correct |
| 14 |
Correct |
3607 ms |
75880 KB |
Output is correct |
| 15 |
Execution timed out |
5035 ms |
84544 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
