제출 #331863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331863		phathnv	Furniture (JOI20_furniture)	C++11	100 / 100	373 ms	21136 KiB

furniture

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1002;
const int dx[8] = {-1, 0, 0, 1};
const int dy[8] = {0, -1, 1, 0};

int m, n, q, a[N][N], imp[N][N], cnt[2 * N];
bool d[N][N];

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

void update(int x, int y){
    if (!imp[x][y])
        return;
    imp[x][y] = 0;
    cnt[x + y]--;
    if (!imp[x - 1][y + 1]){
        update(x - 1, y);
        update(x, y + 1);
    }
    if (!imp[x + 1][y - 1]){
        update(x, y - 1);
        update(x + 1, y);
    }
}

void solve(){
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            imp[i][j] = 1;

    memset(d, 0, sizeof(d));
    d[1][1] = 1;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++){
            d[i][j] |= d[i - 1][j];
            d[i][j] |= d[i][j - 1];
            if (a[i][j])
                d[i][j] = 0;
            imp[i][j] &= d[i][j];
        }

    memset(d, 0, sizeof(d));
    d[m][n] = 1;
    for(int i = m; i >= 1; i--)
        for(int j = n; j >= 1; j--){
            d[i][j] |= d[i + 1][j];
            d[i][j] |= d[i][j + 1];
            if (a[i][j])
                d[i][j] = 0;
            imp[i][j] &= d[i][j];
        }

    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            if (imp[i][j])
                cnt[i + j]++;

    cin >> q;
    while (q--){
        int x, y;
        cin >> x >> y;
        if (!imp[x][y]){
            cout << "1\n";
            continue;
        }
        if (cnt[x + y] == 1){
            cout << "0\n";
            continue;
        }
        update(x, y);
        cout << "1\n";
    }
}

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

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