oj.uz

Submission #1114728

# Submission time Handle Problem Language Result Execution time Memory
1114728 2024-11-19T13:27:54 Z ReLice Furniture (JOI20_furniture) C++17
100 / 100
 227 ms 36680 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 3 ms 4688 KB Output is correct
5 Correct 3 ms 4688 KB Output is correct
6 Correct 3 ms 4576 KB Output is correct
7 Correct 3 ms 4688 KB Output is correct
8 Correct 3 ms 4688 KB Output is correct
9 Correct 4 ms 4688 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 3 ms 4688 KB Output is correct
5 Correct 3 ms 4688 KB Output is correct
6 Correct 3 ms 4576 KB Output is correct
7 Correct 3 ms 4688 KB Output is correct
8 Correct 3 ms 4688 KB Output is correct
9 Correct 4 ms 4688 KB Output is correct
10 Correct 8 ms 2896 KB Output is correct
11 Correct 3 ms 2640 KB Output is correct
12 Correct 118 ms 30724 KB Output is correct
13 Correct 49 ms 27076 KB Output is correct
14 Correct 192 ms 33476 KB Output is correct
15 Correct 191 ms 32808 KB Output is correct
16 Correct 191 ms 33608 KB Output is correct
17 Correct 227 ms 36144 KB Output is correct
18 Correct 214 ms 33864 KB Output is correct
19 Correct 218 ms 36680 KB Output is correct
20 Correct 206 ms 36572 KB Output is correct
21 Correct 208 ms 36532 KB Output is correct