//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define F first
#define S second
#define pb push_back
#define sze size()
#define all(x) x.begin() , x.end()
#define wall__ cout << "--------------------------------------\n";
#define kids int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);
typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;
const ll N = 1e3 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 32;
int n, m;
bitset < N > dp[N], lf[N], rg[N];
bool bl[N][N];
void upd (int x, int y) {
if (dp[x][y] == 0) return;
dp[x][y] = 0;
vector < pii > q; int it = 0; q.pb({x, y});
while (it < q.sze) {
int r = q[it].F, c = q[it].S; ++it;
if (dp[r - 1][c] == 1 && dp[r - 1][c + 1] == 0) {
dp[r - 1][c] = 0; q.pb({r - 1, c});
}
if (dp[r][c - 1] == 1 && dp[r + 1][c - 1] == 0) {
dp[r][c - 1] = 0; q.pb({r, c - 1});
}
}
q.clear(); it = 0; q.pb({x, y});
while (it < q.sze) {
int r = q[it].F, c = q[it].S; ++it;
if (dp[r + 1][c] == 1 && dp[r + 1][c - 1] == 0) {
dp[r + 1][c] = 0; q.pb({r + 1, c});
}
if (dp[r][c + 1] == 1 && dp[r - 1][c + 1] == 0) {
dp[r][c - 1] = 0; q.pb({r, c + 1});
}
}
}
void solve () {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = 1;
cin >> bl[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (bl[i][j]) upd(i, j);
}
}
lf[0][0] = 1;
for (int i = 1; i < N; i++) {
lf[i] = lf[i - 1]; lf[i][i] = 1;
}
rg[N - 1][N - 1] = 1;
for (int i = N - 2; i >= 0; --i) {
rg[i] = rg[i + 1]; rg[i][i] = 1;
}
int q; cin >> q;
while(q--) {
int x, y; cin >> x >> y;
if (dp[x][y] == 0) {
cout << 1 << '\n';
bl[x][y] = 1;
upd(x, y);
} else {
bitset < N > a, b;
a = (dp[x + 1] & lf[y - 1]); b = (dp[x - 1] & rg[y + 1]);
int z = a.count() + b.count();
if (z == 0) cout << 0 << '\n';
else {
cout << 1 << '\n';
upd(x, y);
}
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {solve();}
return 0;
}
/*
*/
//shrek will AC this;
Compilation message
furniture.cpp: In function 'void upd(int, int)':
furniture.cpp:46:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | while (it < q.sze) {
| ^
furniture.cpp:56:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | while (it < q.sze) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
