Submission #499060

#	Time	Username	Problem	Language	Result	Execution time	Memory
499060		khoabright	Furniture (JOI20_furniture)	C++17	0 / 100	2 ms	1100 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define all(x) x.begin(), x.end()

const int N = 1005;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

int id[N][N], R[N][N], vst[N][N];
int cnt[2 * N];
int n, m;

void dfs(int x, int y) {
    if (vst[x][y]) return;
    vst[x][y] = 1;
    if (R[x][y] == 1) return;
    if (x == n && y == m) {
        R[x][y] = 0;
        ++cnt[x + y];
        return;
    }

    R[x][y] = 1;
    rep(k, 0, 1) {
        int xx = x + dx[k];
        int yy = y + dy[k];
        if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
        dfs(xx, yy);
        R[x][y] &= R[xx][yy];
    }
    //cout<<"x,y,x+y,cnt,R="<<x<<' '<<y<<' '<<x+y<<' '<<cnt[x+y]<<' '<<R[x][y]<<'\n';
    cnt[x + y] += (R[x][y] == 0);
}

void update(int x, int y, int px, int py) {
   // cout<<"x,y="<<x<<' '<<y<<'\n';
    rep(k, 0, 3) {
        int xx = x + dx[k];
        int yy = y + dy[k];

        if (xx < 1 || xx > n || yy < 1 || yy > m || R[xx][yy] == 1) continue;
        if (R[xx - 1][yy] && R[xx][yy - 1]) {
            R[xx][yy] = 1;
        }
        if (R[xx + 1][yy] && R[xx][yy + 1]) {
            R[xx][yy] = 1;
        }
        if (R[xx][yy]) {
            --cnt[xx + yy];
            update(xx, yy, x, y);
        }
    }
}

void solve() {
    cin >> n >> m;
    rep(x, 1, n) rep(y, 1, m) {
        cin >> R[x][y];
        if (R[x][y] == 0) R[x][y] = 2;
    }
    dfs(1, 1);
    rep(x, 1, n) rep(y, 1, m) if (R[x][y] == 2) R[x][y] = 1;
//    cout<<'\n';
//    rep(i, 1, n)  rep(j, 1, m){
//        cout << R[i][j]<<" \n"[j == m];
//    }

    int q; cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        //cout << "R,cnt="<<R[x][y]<<' '<<cnt[x+y]<<'\n';
        if (R[x][y] == 1) {
            cout << "1\n";
            continue;

        }
        if (cnt[x + y] <= 1) {
            cout << "0\n";
            continue;
        }

        cout << "1\n";
        R[x][y] = 1;
        --cnt[x + y];
        update(x, y, 0, 0);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}

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