Submission #1191950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191950		Seb	Furniture (JOI20_furniture)	C++20	100 / 100	143 ms	19136 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

using vll = vector<ll>;
using pll = pair<ll,ll>;

#define pb push_back
#define MP make_pair
#define f first
#define s second
#define mid ((l+r)>>1)
#define SZ(x) (int)(x.size())
#define MP make_pair
#define all(x) x.begin(), x.end()

const ll MAXN = 1e3 + 5;
const ll MOD = 998244353;
const ll INF = 1e16;

vector<pll> aux;
ll in[MAXN][MAXN], out[MAXN][MAXN];
bool vis[MAXN][MAXN];
ll N, M;

void borra_nodos() {
    while (!aux.empty()) {
        auto p = aux.back();
        aux.pop_back();
        if (vis[p.f][p.s]) continue;

        vis[p.f][p.s] = true;

        if (p.f) {
            out[p.f - 1][p.s]--;
            if (!vis[p.f - 1][p.s] && (!in[p.f - 1][p.s] || !out[p.f - 1][p.s]))
                aux.pb(MP(p.f - 1, p.s));
        }
        if (p.s) {
            out[p.f][p.s - 1]--;
            if (!vis[p.f][p.s - 1] && (!in[p.f][p.s - 1] || !out[p.f][p.s - 1]))
                aux.pb(MP(p.f, p.s - 1));
        }
        if (p.f < N - 1) {
            in[p.f + 1][p.s]--;
            if (!vis[p.f + 1][p.s] && (!in[p.f + 1][p.s] || !out[p.f + 1][p.s]))
                aux.pb(MP(p.f + 1, p.s));
        }
        if (p.s < M - 1) {
            in[p.f][p.s + 1]--;
            if (!vis[p.f][p.s + 1] && (!in[p.f][p.s + 1] || !out[p.f][p.s + 1]))
                aux.pb(MP(p.f, p.s + 1));
        }
    }
}

bool check(ll x, ll y) {
    if (vis[x][y]) return true;

    ll X = 2;
    for (int j = y + 1; j < M; j++) {
        if (vis[x][j]) { X = 1; continue; }
        if (in[x][j] >= X) return true;
    }
    X = 2;
    for (int i = x + 1; i < N; i++) {
        if (vis[i][y]) { X = 1; continue; }
        if (in[i][y] >= X) return true;
    }
    return false;
}

void tc() {
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++) {
        ll a; cin >> a;
        in[i][j] = out[i][j] = 2;
        if (a) aux.pb(MP(i, j));
    }

    for (int i = 0; i < N; i++) in[i][0]--;
    for (int j = 0; j < M; j++) in[0][j]--;
    for (int i = 0; i < N; i++) out[i][M - 1]--;
    for (int j = 0; j < M; j++) out[N - 1][j]--;

    in[0][0] = out[N - 1][M - 1] = INF;

    borra_nodos();

    ll Q; cin >> Q;
    while (Q--) {
        ll x, y; cin >> x >> y;

        if (check(x - 1, y - 1)) {
            aux.pb(MP(x - 1, y - 1));

            borra_nodos();

            cout << "1\n";
        }

        else cout << "0\n";
    }
}

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

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