#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e3 + 6;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
///Road to EF
ll n,m,a[N][N],was[N][N],live[N][N],x,y,Q;
ll dx[4] = {0,0,1,-1};
ll dy[4] = {1,-1,0,0};
ll knot[N][N],got;
bool chk(ll x,ll y){
return x <= n&&y <= m&&x > 0&&y > 0&&!a[x][y];
}
ll f(ll x,ll y){
if (x == n&&y == m) return was[x][y] = 1;
if (was[x][y] != -1) return was[x][y];
ll ans = 0;
if (chk(x + 1,y)) ans = max(ans,f(x + 1,y));
if (chk(x,y + 1)) ans = max(ans,f(x,y + 1));
return was[x][y] = ans;
}
bool Is_live(ll x,ll y){
bool f1 = 0,f2 = 0;
f1 = max(live[x][y + 1],live[x + 1][y]);
f2 = max(live[x - 1][y],live[x][y - 1]);
return min(f1,f2);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "tst"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>n>>m; memset(was,-1,sizeof(was));
for (ll i = 1;i <= n;i++)
for (ll j = 1;j <= m;j++) cin>>a[i][j];
for (ll i = 1;i <= n;i++)
for (ll j = 1;j <= m;j++) live[i][j] = f(i,j);
bool firstTime = 0;
cin>>Q;
while(Q--){
cin>>x>>y;
queue<LL> q; q.push({x,y});
if (firstTime){
if (!got){
if (live[x][y]) cout<<0;
else cout<<1; cout<<"\n";
}
else{
if (knot[x][y]) cout<<0;
else{
if (live[x][y]) cout<<1,got = 0;
else cout<<1; cout<<"\n";
}
}
continue;
}
a[x][y] = 1;
while(!q.empty()){
LL t = q.front(); q.pop();
live[t.fs][t.sc] = 0;
for (ll i = 0;i < 4;i++){
ll u = t.fs + dx[i],v = t.sc + dy[i];
if (chk(u,v) && !Is_live(u,v) && live[u][v]) q.push({u,v});
}
}
if (live[1][1]) cout<<1<<"\n";
else{
cout<<0; cout<<"\n"; firstTime = 1; a[x][y] = 0; memset(was,-1,sizeof(was));
for (ll i = 1;i <= n;i++)
for (ll j = 1;j <= m;j++) live[i][j] = f(i,j);
for (ll i = 1;i <= n;i++)
for (ll j = 1;j <= m;j++){
ll cnt = 0;
for(ll k = 0;k < 4;k++) cnt += live[i + dx[k]][j + dy[k]];
if (cnt > 2) knot[i][j] = 1,got = 1;
}
}
}
}
Compilation message
furniture.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
1 | #pragma GCC optimization "O2"
|
furniture.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
furniture.cpp: In function 'int main()':
furniture.cpp:62:17: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
62 | else cout<<1; cout<<"\n";
| ^~~~
furniture.cpp:62:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
62 | else cout<<1; cout<<"\n";
| ^~~~
furniture.cpp:68:21: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
68 | else cout<<1; cout<<"\n";
| ^~~~
furniture.cpp:68:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
68 | else cout<<1; cout<<"\n";
| ^~~~
furniture.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
46 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4812 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
5452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4812 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
5452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
