Submission #1238320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238320		dprto	Furniture (JOI20_furniture)	C++20	100 / 100	146 ms	3368 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define F(i, l, r) for(ll i = l; i <= r; ++i)
#define E(i, l, r) for(int i = l; i >= r; --i)
#define MASK(i) (1 << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define eb emplace_back
const ll mod = 1e9 + 7;
const int ars = 1e3 + 5;
const int ii = 1e9;
const ll il = 1e18;

int n, m, q;
bool a[ars][ars];
int diag[2005];
queue<pair<int, int>> qq;
void Set(int x, int y) {
    if(!a[x][y]) {
        a[x][y] = 1;
        --diag[x + y];
        qq.emplace(x, y);
    }
}

int process(int x, int y) {
    if(a[x][y]) {
        return 1;
    }
    if(diag[x + y] == 1) {
        return 0;
    }

    Set(x, y);
    while(!qq.empty()) {
        auto [x, y] = qq.front(); qq.pop();
        if(a[x - 1][y + 1]) {
            Set(x - 1, y);
            Set(x, y + 1);
        }
        if(a[x + 1][y - 1]) {
            Set(x, y - 1);
            Set(x + 1, y);
        }
    }
    return 1;

}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    F(i, 0, n + 1) F(j, 0, m + 1) a[i][j] = 1;
    F(i, 1, n) F(j, 1, m) {
        a[i][j] = 0;
        ++diag[i + j];
    }
    
    int k;
    F(i, 1, n) F(j, 1, m) {
        cin >> k;
        if(k) process(i, j);
    }

    cin >> q;
    int x, y;
    F(i, 1, q) {
        cin >> x >> y;
        cout << process(x, y) << "\n";
    }



    return 0;
}

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