Submission #595530

#	Time	Username	Problem	Language	Result	Execution time	Memory
595530		SOCIOPATE	Furniture (JOI20_furniture)	C++17	0 / 100	5 ms	468 KiB

furniture

#include <bits/stdc++.h>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <cmath>
#include <assert.h>
#include <ctime>
#include <math.h>
#include <queue>
#include <string>
#include <numeric>
#include <fstream>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <stack>
#include <random>
#include <list>
#include <bitset>
#include <algorithm>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define pll pair<ll, ll>
#define pii pair<int, int>
#define pdd pair<ld, ld>
#define ff first
#define ss second
#define all(v) v.begin(),v.end()

typedef tree<
    pii,
    null_type,
    less<pii>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordset;


#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-Os")

ll INF = 2e18;

//mt19937 gen(time(0));

ll gcd(ll n, ll m){
    while(n != 0 && m != 0){
        if(n > m) n %= m;
        else m %= n;
    }
    return n + m;
}

ll lcm(ll n, ll m){
    ll nod = gcd(n, m);
    return n / nod * m;
}

ll mod = 1e9 + 7;

ll binpow(ll n, ll m){
    if(m == 0) return 1;
    if(m % 2ll == 1) {
        return (binpow(n, m - 1ll) * 1ll * n) % mod;
    }
    ll b = binpow(n, m / 2);
    return (b * 1ll * b) % mod;

}

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> may(n + 2, vector<bool>(m + 2, 0));
    vector<int> cnt(10000, 0);
    vector<vector<int>> a(n + 2, vector<int>(m + 2));
    vector<pii> qq;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            cnt[i + j]++;
            may[i][j] = 1;
            if(a[i][j] == 1){
                qq.push_back({i, j});
            }
        }
    }
    queue<pii> st;
    for(pii& p : qq){
        cnt[p.ff + p.ss]--;
        may[p.ff][p.ss] = 0;
        st.push({p.ff - 1, p.ss});
        st.push({p.ff, p.ss - 1});
        st.push({p.ff + 1, p.ss});
        st.push({p.ff, p.ss + 1});
        while(st.size()){
            int i = st.front().ff, j = st.front().ss;
            st.pop();
            if(i <= 0 || j <= 0 || i > n || j > m || (j == 1 && i == 1) || (j == m && i == n)) continue;
            bool was = 0;
            if(!may[i - 1][j] && !may[i][j - 1]){
                //cout << i << " " << j << '\n';
                may[i][j] = 0;
                was = 1;
                cnt[i + j]--;
                if(may[i + 1][j]) st.push({i + 1, j});
                if(may[i][j + 1]) st.push({i, j + 1});
            }
            if(!may[i + 1][j] && !may[i][j + 1]){
                //cout << i << " " << j << '\n';
                may[i][j] = 0;
                if(!was) cnt[i + j]--;
                if(may[i - 1][j]) st.push({i - 1, j});
                if(may[i][j - 1]) st.push({i, j - 1});
            }
        }
    }
    int q;
    cin >> q;
    for(int h = 0; h < q; h++){
        int x, y;
        cin >> x >> y;
        if(!may[x][y]) {
            cout << 1 << '\n';
            continue;
        }
        if(cnt[x + y] == 1) {
            cout << 0 << '\n';
            continue;
        }
        may[x][y] = 0;
        cout << 1 << '\n';
        queue<pii> st;
        st.push({x - 1, y});
        st.push({x, y - 1});
        st.push({x + 1, y});
        st.push({x, y + 1});
        cnt[x + y]--;
        while(st.size()){
            int i = st.front().ff, j = st.front().ss;
            st.pop();
            if(i <= 0 || j <= 0 || i > n || j > m || (j == 1 && i == 1) || (j == m && i == n)) continue;
            bool was = 0;
            if(!may[i - 1][j] && !may[i][j - 1]){
                may[i][j] = 0;
                was = 1;
                cnt[i + j]--;
                if(may[i + 1][j]) st.push({i + 1, j});
                if(may[i][j + 1]) st.push({i, j + 1});
            }
            if(!may[i + 1][j] && !may[i][j + 1]){
                may[i][j] = 0;
                if(!was) cnt[i + j]--;
                if(may[i - 1][j]) st.push({i - 1, j});
                if(may[i][j - 1]) st.push({i, j - 1});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int tt;
    //cin >> tt;
	tt = 1;
	while (tt--) {
		solve();
	}
	return 0;
}

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