Submission #401212

#	Time	Username	Problem	Language	Result	Execution time	Memory
401212		cpp219	Furniture (JOI20_furniture)	C++14	0 / 100	5 ms	5452 KiB

furniture

#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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95