Submission #1156585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156585		Hamed_Ghaffari	Furniture (JOI20_furniture)	C++20	100 / 100	144 ms	3420 KiB

furniture

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

const int MXN = 1003;

int n, m, q;
int cnt[MXN+MXN];
bool mark[MXN][MXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool SC(int i, int j) {
    if(i<1 || i>n || j<1 || j>m || mark[i][j] || (i==1 && j==1) || (i==n && j==m)) return 0;
    if((i==1 || mark[i-1][j]) && (j==1 || mark[i][j-1])) return 1;
    if((i==n || mark[i+1][j]) && (j==m || mark[i][j+1])) return 1;
    return 0;
}

void dfs(int i, int j) {
    if(!SC(i, j)) return;
    mark[i][j] = 1;
    cnt[i+j]--;
    for(int d=0; d<4; d++)
        dfs(i+dx[d], j+dy[d]);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            cin >> mark[i][j];
            cnt[i+j] += 1-mark[i][j];
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            dfs(i, j);
    cin >> q;
    while(q--) {
        int i, j;
        cin >> i >> j;
        if(mark[i][j]) {
            cout << "1\n";
            continue;
        }
        if(cnt[i+j]>1) {
            cout << "1\n";
            mark[i][j] = 1; cnt[i+j] --;
            for(int d=0; d<4; d++)
                dfs(i+dx[d], j+dy[d]);
        }
        else cout << "0\n";
    }
    return 0;
}

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