#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e15 + 7, inf = 1e16;
const int mxn = 2e3 + 5;
int n, m, q;
int a[1005][1005];
int cnt[2005];
bool bad[1005][1005];
bool ck(int x, int y){
if(x == n && y == m)return(0);
if(bad[x][y])return(0);
if(bad[x + 1][y] && bad[x][y + 1])return(1);
if(bad[x - 1][y] && bad[x][y - 1])return(1);
return(0);
}
bool inside(int x, int y){
return(x >= 1 && y >= 1 && x <= n && y <= m);
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
if(a[i][j] == 1){
bad[i][j] = 1;
}else{
cnt[i + j]++;
}
}
}
for(int i = 1; i <= n; i++)bad[i][m + 1] = 1;
for(int i = 1; i <= m; i++)bad[n + 1][i] = 1;
queue<pii>q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == 1){
for(int k = 0; k < 4; k++){
if(inside(i + x[k], j + y[k]) && !bad[i + x[k]][j + y[k]]){
q.push({i + x[k], j + y[k]});
}
}
}
}
}
while(!q.empty()){
auto [cox, coy] = q.front(); q.pop();
//cout << cox << ' ' << coy << " ";
if(ck(cox, coy)){
bad[cox][coy] = 1; cnt[cox + coy]--;
for(int i = 0; i < 4; i++){
int nwx = cox + x[i], nwy = coy + y[i];
if(inside(nwx, nwy) && !bad[nwx][nwy]){
q.push({nwx, nwy});
}
}
}
}
for(int i = 2; i <= n + m; i++){
assert(cnt[i] >= 1);
}
int qq; cin >> qq;
while(qq--){
int cox, coy; cin >> cox >> coy;
if(cnt[cox + coy] == 0){
cout << cox + coy << "\n";
}
if(bad[cox][coy]){
cout << 1 << "\n";
}
else if(cnt[cox + coy] == 1){
cout << 0 << "\n";
continue;
}else{
vt<pii>rem;
bool ok = 1;
rem.pb({cox, coy});
int xx = cox, yy = coy;
bad[cox][coy] = 1; cnt[cox + coy]--;
for(int i = 0; i < 4; i++){
int nwx = cox + x[i], nwy = coy + y[i];
if(inside(nwx, nwy) && !bad[nwx][nwy]){
q.push({nwx, nwy});
}
}
while(!q.empty()){
auto [cox, coy] = q.front(); q.pop();
if(ck(cox, coy)){
//assert(cox == xx || cox + coy != xx + yy);
bad[cox][coy] = 1; cnt[cox + coy]--;
if(cnt[cox+ coy] == 0){
ok = 0;
}
rem.pb({cox, coy});
for(int i = 0; i < 4; i++){
int nwx = cox + x[i], nwy = coy + y[i];
if(inside(nwx, nwy) && !bad[nwx][nwy]){
q.push({nwx, nwy});
}
}
}
}
if(ok)cout << 1 << "\n";
else{
cout << 0 << "\n";
for(auto [xx, yy]: rem){
bad[xx][yy] = 0; cnt[xx + yy]++;
}
}
}
}
return(0);
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | auto [cox, coy] = q.front(); q.pop();
| ^
furniture.cpp:110:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
110 | auto [cox, coy] = q.front(); q.pop();
| ^
furniture.cpp:130:25: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
130 | for(auto [xx, yy]: rem){
| ^
furniture.cpp:100:17: warning: unused variable 'xx' [-Wunused-variable]
100 | int xx = cox, yy = coy;
| ^~
furniture.cpp:100:27: warning: unused variable 'yy' [-Wunused-variable]
100 | int xx = cox, yy = coy;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
852 KB |
Output is correct |
| 3 |
Correct |
2 ms |
852 KB |
Output is correct |
| 4 |
Correct |
3 ms |
852 KB |
Output is correct |
| 5 |
Correct |
3 ms |
852 KB |
Output is correct |
| 6 |
Correct |
3 ms |
852 KB |
Output is correct |
| 7 |
Correct |
3 ms |
980 KB |
Output is correct |
| 8 |
Correct |
8 ms |
980 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
852 KB |
Output is correct |
| 3 |
Correct |
2 ms |
852 KB |
Output is correct |
| 4 |
Correct |
3 ms |
852 KB |
Output is correct |
| 5 |
Correct |
3 ms |
852 KB |
Output is correct |
| 6 |
Correct |
3 ms |
852 KB |
Output is correct |
| 7 |
Correct |
3 ms |
980 KB |
Output is correct |
| 8 |
Correct |
8 ms |
980 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1064 KB |
Output is correct |
| 10 |
Correct |
33 ms |
1220 KB |
Output is correct |
| 11 |
Correct |
3 ms |
596 KB |
Output is correct |
| 12 |
Correct |
146 ms |
11604 KB |
Output is correct |
| 13 |
Correct |
51 ms |
10020 KB |
Output is correct |
| 14 |
Correct |
214 ms |
16000 KB |
Output is correct |
| 15 |
Correct |
222 ms |
14808 KB |
Output is correct |
| 16 |
Correct |
284 ms |
15800 KB |
Output is correct |
| 17 |
Correct |
220 ms |
16348 KB |
Output is correct |
| 18 |
Correct |
220 ms |
16148 KB |
Output is correct |
| 19 |
Correct |
231 ms |
17616 KB |
Output is correct |
| 20 |
Correct |
1163 ms |
20524 KB |
Output is correct |
| 21 |
Correct |
3351 ms |
20924 KB |
Output is correct |
