Submission #1114728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114728		ReLice	Furniture (JOI20_furniture)	C++17	100 / 100	227 ms	36680 KiB

furniture

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define sz size()
#define bc back()
#define ins insert
#define fr first
#define sc second
#define ar array
#define endl "\n"
#define all(x) x.begin(), x.end()

using namespace std;

void start(){
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
}

const ll N = 3e3 + 7;
const ll mod = 1e9 + 7;

ll a[N][N];
ll cnt[N];

signed main(){
    start();

    ll n, m;
    ll i, j;

    cin>>n>>m;

    vector<pair<ll,ll>> v;

    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>a[i][j];

            cnt[i + j] ++;

            if(a[i][j] == 1) {
                v.pb({i, j});
            }

            a[i][j] = 0;
        }
    }

    ll dir[6][2] = {
        {-1, 1},
        {-1, 0},
        {0, 1},
        {1, -1},
        {1, 0},
        {0, -1},
    };

    auto del = [&] (ll i, ll j){
        queue<ar<ll, 2>> q;
        q.push({i, j});
        a[i][j] = 1;
        cnt[i + j] --;

        auto ok = [&](ll x, ll y){return (x >= 1 && x <= n && y >= 1 && y <= m);};

        while(q.size()){
            auto cur = q.front();
            q.pop();

            for(ll k=0;k<6;k+=3){
                ll x = cur[0] + dir[k][0], y = cur[1] + dir[k][1];

                if(!ok(x, y) || a[x][y]){
                    for(auto d : {k + 1, k + 2}){
                        ll i = cur[0] + dir[d][0], j = cur[1] + dir[d][1];

                        if(ok(i, j) && !a[i][j]){
                            a[i][j] = 1;
                            cnt[i + j] --;
                            q.push({i, j});
                        }
                    }
                }
            }
        }
    };

    for(auto i : v){
        if(!a[i.fr][i.sc]){
            del(i.fr, i.sc);
        }
    }

    ll q;
    cin>>q;

    while(q--){
        ll x, y;

        cin>>x>>y;

        if(a[x][y])cout<<1<<endl;

        else if(cnt[x + y] == 1) cout<<0<<endl;

        else {
            del(x, y);
            cout<<1<<endl;
        }
    }
}
/*
2 1 0
10
1

*/

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