Submission #1238292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238292		bncodero_o123	Furniture (JOI20_furniture)	C++20	0 / 100	1 ms	576 KiB

furniture

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define name "code"
using namespace std;

const int max_n= 1e3;
int n, m;
bool a[max_n + 2][max_n + 2];
bool R[max_n + 2][max_n + 2];

int cnt[2 * max_n + 2];
bool tow[max_n + 2][max_n + 2];
bool bac[max_n + 2][max_n + 2];

void prep() {
    for(int i= 1; i <= n; ++i)
        for(int j= 1; j <= m; ++j)
            if(!a[i][j]) {
                tow[i][j]= tow[i - 1][j] | tow[i][j - 1];
                if(i == 1 && j == 1) tow[i][j]= 1;
            }

    for(int i= n; i > 0; --i)
        for(int j= m; j > 0; --j)
            if(!a[i][j]) {
                bac[i][j]= bac[i + 1][j] | bac[i][j + 1];
                if(i == n && j == m) bac[i][j]= 1;
            }

    for(int i= 1; i <= n; ++i)
        for(int j= 1; j <= m; ++j) {
            R[i][j]= tow[i][j] & bac[i][j];
            cnt[i + j] += R[i][j];
        }
}

bool check1(int u, int v) {
    if(R[u][v]) {
        bool ok= 0;
        if(u < n) ok |= R[u + 1][v];
        if(v < m) ok |= R[u][v + 1];
        return ok;
    }
    return 0;
}

bool check2(int u, int v) {
    if(R[u][v]) {
        bool ok= 0;
        if(u > 1) ok |= R[u - 1][v];
        if(v > 1) ok |= R[u][v - 1];
        return ok;
    }
    return 0;
}

void upd(int x, int y) {
    --cnt[x + y], R[x][y]= 0;

    queue<pii> q;
    if(x > 1 && check1(x - 1, y)) q.push(make_pair(x - 1, y));
    if(y > 1 && check1(x, y - 1)) q.push(make_pair(x, y - 1));

    while(q.size()) {
        auto [u, v]= q.front(); q.pop();
        R[u][v]= 0, --cnt[u + v];
        if(u > 1 && check1(u - 1, v)) q.push(make_pair(u - 1, v));
        if(v > 1 && check1(u, v - 1)) q.push(make_pair(u, v - 1));
    }

    if(x < n && check2(x + 1, y)) q.push(make_pair(x + 1, y));
    if(y < m && check2(x, y + 1)) q.push(make_pair(x, y + 1));

    while(q.size()) {
        auto [u, v]= q.front(); q.pop();
        R[u][v]= 0, --cnt[u + v];
        if(u < n && check2(u + 1, v)) q.push(make_pair(u + 1, v));
        if(v < m && check2(u, v + 1)) q.push(make_pair(u, v + 1));
    }
}

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

    int q; cin >> q;
    while(q--) {
        int x, y; cin >> x >> y;
        if(!R[x][y] || cnt[x + y] > 1) cout << 1 << '\n', upd(x, y);
        else cout << 0 << '\n';
    }
}

signed main() {
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    int T= 1;
    for(; T; --T) solve();

    return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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