#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];
bitset<N> S[N], S2[N];
bitset<N> SS[N], SS2[N];
#define dobre(x, y) (czy[0][x][y]&czy[1][x][y])
void upd(int x, int y){
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]);
S[x][y]=dobre(x, y);
S2[y][x]=dobre(x, y);
SS[x][N-y]=dobre(x, y);
SS2[y][N-x]=dobre(x, y);
}
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].count() && S2[y].count()){
int mx=S[x]._Find_first();
int Mx=N-SS[x]._Find_first();
int my=S2[y]._Find_first();
int My=N-SS2[y]._Find_first();
//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:109: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]
109 | for(int i=0; i<todo.size(); i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
Output is correct |
| 2 |
Correct |
2 ms |
724 KB |
Output is correct |
| 3 |
Correct |
4 ms |
724 KB |
Output is correct |
| 4 |
Correct |
4 ms |
724 KB |
Output is correct |
| 5 |
Correct |
5 ms |
724 KB |
Output is correct |
| 6 |
Correct |
7 ms |
724 KB |
Output is correct |
| 7 |
Correct |
5 ms |
852 KB |
Output is correct |
| 8 |
Correct |
5 ms |
852 KB |
Output is correct |
| 9 |
Correct |
4 ms |
728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
Output is correct |
| 2 |
Correct |
2 ms |
724 KB |
Output is correct |
| 3 |
Correct |
4 ms |
724 KB |
Output is correct |
| 4 |
Correct |
4 ms |
724 KB |
Output is correct |
| 5 |
Correct |
5 ms |
724 KB |
Output is correct |
| 6 |
Correct |
7 ms |
724 KB |
Output is correct |
| 7 |
Correct |
5 ms |
852 KB |
Output is correct |
| 8 |
Correct |
5 ms |
852 KB |
Output is correct |
| 9 |
Correct |
4 ms |
728 KB |
Output is correct |
| 10 |
Correct |
10 ms |
980 KB |
Output is correct |
| 11 |
Correct |
4 ms |
552 KB |
Output is correct |
| 12 |
Correct |
447 ms |
5960 KB |
Output is correct |
| 13 |
Correct |
86 ms |
4244 KB |
Output is correct |
| 14 |
Correct |
555 ms |
6592 KB |
Output is correct |
| 15 |
Correct |
784 ms |
13576 KB |
Output is correct |
| 16 |
Correct |
383 ms |
14156 KB |
Output is correct |
| 17 |
Correct |
438 ms |
14924 KB |
Output is correct |
| 18 |
Correct |
715 ms |
14588 KB |
Output is correct |
| 19 |
Correct |
430 ms |
16176 KB |
Output is correct |
| 20 |
Correct |
431 ms |
17460 KB |
Output is correct |
| 21 |
Correct |
341 ms |
17328 KB |
Output is correct |
