Submission #683781

#	Time	Username	Problem	Language	Result	Execution time	Memory
683781		Fysty	Furniture (JOI20_furniture)	C++17	100 / 100	231 ms	15792 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back

const int N=1005;
int n,m;
bool has[N][N],can[N][N],dp[N][N],vis[N][N];
int cnt[N*2];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
queue<pii> q;
void check(int x,int y)
{
    if(x<1||x>n||y<1||y>m) return;
    if(vis[x][y]) return;
    bool bad=0;
    if((x>1||y>1)&&dp[x-1][y]==0&&dp[x][y-1]==0) bad=1;
    if((x<n||y<m)&&dp[x+1][y]==0&&dp[x][y+1]==0) bad=1;
    //cout<<x<<" "<<y<<" bad?"<<bad<<"\n";
    if(bad)
    {
        vis[x][y]=1;
        dp[x][y]=0;
        cnt[x+y]--;
        q.push({x,y});
    }
}
signed main()
{
    MottoHayaku
    cin>>n>>m;
    rep1(i,n) rep1(j,m) cin>>has[i][j];
    rep1(i,n) rep1(j,m) dp[i][j]=1;
    can[1][1]=1;
    rep1(i,n)
    {
        rep1(j,m)
        {
            if(i>1||j>1) can[i][j]=can[i-1][j]|can[i][j-1];
            can[i][j]&=(!has[i][j]);
            dp[i][j]&=can[i][j];
        }
    }
    rep1(i,n) rep1(j,m) can[i][j]=0;
    can[n][m]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            if(i<n||j<m) can[i][j]=can[i+1][j]|can[i][j+1];
            can[i][j]&=(!has[i][j]);
            dp[i][j]&=can[i][j];
        }
    }
    rep1(i,n) rep1(j,m)
    {
        //cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
        if(dp[i][j]==0)
        {
            vis[i][j]=1;
            q.push({i,j});
        }
        else cnt[i+j]++;
    }
    int Q;
    cin>>Q;
    while(Q--)
    {
        int x,y;
        cin>>x>>y;
        while(!q.empty())
        {
            int tx=q.front().F,ty=q.front().S;
            //cout<<tx<<" "<<ty<<"\n";
            q.pop();
            rep(d,4) check(tx+dx[d],ty+dy[d]);
        }
        if(!dp[x][y]) cout<<"1\n";
        else
        {
            if(cnt[x+y]==1) cout<<"0\n";
            else
            {
                cout<<"1\n";
                dp[x][y]=0;
                vis[x][y]=1;
                cnt[x+y]--;
                q.push({x,y});
            }
        }
    }
}

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