Submission #1145788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145788		fatman87878	Furniture (JOI20_furniture)	C++20	0 / 100	1 ms	1604 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=1e3+5;

int n,m,Q,cnt[maxN+maxN],c[maxN][maxN],in[maxN][maxN],out[maxN][maxN];

queue<pair<int,int>> q;

inline bool chk(int x,int y){
    if(x>n||x<1||y>m||y<1||c[x][y])return 0;
    return 1;
}

inline void push(){
    for(int x,y;!q.empty();){
        tie(x,y) = q.front(),q.pop();
        cnt[x+y]--;
        c[x][y] = 1;
        if(chk(x-1,y)&&!(--out[x-1][y]))q.emplace(x-1,y);
        if(chk(x,y-1)&&!(--out[x][y-1]))q.emplace(x,y-1);
        if(chk(x+1,y)&&!(--in[x+1][y]))q.emplace(x+1,y);
        if(chk(x,y+1)&&!(--in[x][y+1]))q.emplace(x,y+1);
    }
}

int main(){
    IOS
    cin>>n>>m;
    for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++){
        cin>>c[i][j],cnt[i+j]++;
        if(c[i][j])q.emplace(i,j);
    }
    for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)if(!c[i][j])out[i][j] = (i!=n)+(j!=m);
    for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)if(!c[i][j])in[i][j] = (i!=1)+(j!=1);
    push();
    /*for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)cout<<c[i][j]<<" \n"[j==m];
    for(int i = 2;i<=n+m;i++)cout<<cnt[i]<<' ';
    cout<<'\n';*/
    cin>>Q;
    for(int x,y;Q--;){
        cin>>x>>y;
        if(c[x][y]||cnt[x+y]>1){
            if(!c[x][y]){
                q.emplace(x,y);
                in[x][y] = 0;
                out[x][y] = 0;
                push();
            }
            cout<<"1\n";
        }
        else cout<<"0\n";
    }
}

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