Submission #372433

#	Time	Username	Problem	Language	Result	Execution time	Memory
372433		Jarif_Rahman	Furniture (JOI20_furniture)	C++17	0 / 100	2 ms	364 KiB

furniture

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, m, cur, cnt;
vector<vector<bool>> v;
vector<bool> block;
vector<int> ff, ls;
vector<vector<bool>> aa, bb;
int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy[8] = {1, -1, 0, 1, -1, 0, 1, -1};
bool check1(int x, int y){
    cnt = 0;
    if(!block[x]){
        if(x == 0) cnt++;
        else if(max(y, ls[x]) >= ff[x-1]-1) cnt++;
    }
    if(x+1 < n && !block[x+1]){
        if(ls[x+1] >= min(y, ff[x])-1) cnt++;
    }
    if(cur-cnt <= 0) return 0;
    return 1;
}
bool check2(int x, int y){
    bool b1 = 0, b2 = 0;
    if(x == n-1) b1 = 1;
    if(y == m-1) b2 = 1;
    for(int i = 0; i < 8; i++){
        int xx = x+dx[i], yy = y+dy[i];
        if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
        b1|=aa[xx][yy];
        b2|=bb[xx][yy];
    }
    return !(b1&b2);
}
void do2(int x, int y){
    bool b1 = 0, b2 = 0;
    if(x == n-1) b1 = 1;
    if(y == m-1) b2 = 1;
    for(int i = 0; i < 8; i++){
        int xx = x+dx[i], yy = y+dy[i];
        if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
        b1|=aa[xx][yy];
        b2|=bb[xx][yy];
    }
    aa[x][y] = b1;
    bb[x][y] = b2;
}
void do1(int x, int y){
    if(!block[x]){
        if(x == 0) block[x] = 1;
        else if(max(y, ls[x]) >= ff[x-1]-1) block[x] = 1;
    }
    if(x+1 < n && !block[x+1]){
        if(ls[x+1] >= min(y, ff[x])-1) block[x+1] = 1;
    }
    ff[x] = min(ff[x], y);
    ls[x] = max(ls[x], y);
    cur-=cnt;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    v = vector<vector<bool>>(n, vector<bool>(m, 0));
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
        bool bl; cin >> bl;
        v[i][j] = bl;
    }
    ff.resize(n, m+1), ls.resize(n, -1);
    block.resize(n, 0);
    aa = vector<vector<bool>>(n, vector<bool>(m, 0)), bb = aa;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
        if(!v[i][j]) continue;
        ff[i] = min(ff[i], j);
        ls[i] = max(ls[i], j);
        if(i == 0 && !block[i]) block[i] = 1;
        else if(j >= ff[i-1]-1) block[i] = 1;
    }
    for(int j = 0; j < m; j++) if(v[n-1][j]) aa[n-1][j] = 1;
    for(int i = 0; i < n; i++) if(v[i][m-1]) bb[i][m-1] = 1;
    for(int i = n-2; i >= 0; i--){
        for(int j = 0; j < m; j++){
            if(!v[i][j]) continue;
            if(aa[i+1][j]) aa[i][j] = 1;
            if(j > 0 && aa[i+1][j-1]) aa[i][j] = 1;
            if(j < m-1 && aa[i+1][j+1]) aa[i][j] = 1;
            if(j > 0 && aa[i][j-1]) aa[i][j] = 1;
            if(j < m-1 && aa[i][j+1]) aa[i][j] = 1;
        }
        for(int j = m-1; j >= 0; j--){
            if(!v[i][j]) continue;
            if(aa[i+1][j]) aa[i][j] = 1;
            if(j > 0 && aa[i+1][j-1]) aa[i][j] = 1;
            if(j < m-1 && aa[i+1][j+1]) aa[i][j] = 1;
            if(j > 0 && aa[i][j-1]) aa[i][j] = 1;
            if(j < m-1 && aa[i][j+1]) aa[i][j] = 1;
        }
    }
    for(int j = m-2; j >= 0; j--){
        for(int i = 0; i < n; i++){
            if(!v[i][j]) continue;
            if(bb[i][j+1]) bb[i][j] = 1;
            if(i > 0 && bb[i-1][j+1]) bb[i][j] = 1;
            if(i < n-1 && bb[i+1][j+1]) bb[i][j] = 1;
            if(i > 0 && bb[i-1][j]) bb[i][j] = 1;
            if(i < n-1 && bb[i+1][j]) bb[i][j] = 1;
        }
        for(int i = n-1; i >= 0; i--){
            if(!v[i][j]) continue;
            if(bb[i][j+1]) bb[i][j] = 1;
            if(i > 0 && bb[i-1][j+1]) bb[i][j] = 1;
            if(i < n-1 && bb[i+1][j+1]) bb[i][j] = 1;
            if(i > 0 && bb[i-1][j]) bb[i][j] = 1;
            if(i < n-1 && bb[i+1][j]) bb[i][j] = 1;
        }
    }
    cur = n;
    for(int i = 0; i < n; i++) if(block[i]) cur--;
    int q; cin >> q;
    while(q--){
        int x, y; cin >> x  >> y; x--, y--;
        if(!check1(x, y) || !check2(x, y)){
            cout << "0\n";
            continue;
        }
        cout << "1\n";
        do1(x, y);
        do2(x, y);
    }
}

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