Submission #1053339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053339		Piokemon	Furniture (JOI20_furniture)	C++17	100 / 100	138 ms	5460 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 1000;
bool blok[N+9][N+9];
bool dasie[N+9][N+9];
bool dasie2[N+9][N+9];
int cnt[2*N+9];

void zab(int x, int y){
    if (!blok[x][y]) cnt[x+y]--;
    blok[x][y]=1;dasie[x][y]=0;dasie2[x][y]=0;
    if (!blok[x+1][y] && dasie[x+1][y]){
        if (blok[x+1][y-1]){dasie[x+1][y]=0;zab(x+1,y);}
    }
    if (!blok[x][y+1] && dasie[x][y+1]){
        if (blok[x-1][y+1]){dasie[x][y+1]=0;zab(x,y+1);}
    }
    if (!blok[x][y-1] && dasie2[x][y-1]){
        if (blok[x+1][y-1]){dasie2[x][y-1]=0;zab(x,y-1);}
    }
    if (!blok[x-1][y] && dasie2[x-1][y]){
        if (blok[x-1][y+1]) {dasie2[x-1][y]=0;zab(x-1,y);}
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin >> n >> m;
    for (int x=1;x<=n;x++){
        for (int y=1;y<=m;y++){
            cin >> blok[x][y];
        }
    }
    for (int x=0;x<=max(n,m);x++){
        blok[0][x]=1;blok[x][0]=1;
        blok[n+1][x]=1;blok[x][m+1]=1;
    }
    dasie[1][1]=1;
    for (int x=1;x<=n;x++){
        for (int y=1;y<=m;y++){
            if (blok[x][y])continue;
            if (dasie[x][y]){
                if (!blok[x+1][y])dasie[x+1][y]=1;
                if (!blok[x][y+1])dasie[x][y+1]=1;
            }
        }
    }
    dasie2[n][m]=1;
    for (int x=n;x>=1;x--){
        for (int y=m;y>=1;y--){
            if (blok[x][y])continue;
            if (dasie2[x][y]){
                if (!blok[x-1][y])dasie2[x-1][y]=1;
                if (!blok[x][y-1])dasie2[x][y-1]=1;
            }
        }
    }
    for (int x=1;x<=n;x++){
        for (int y=1;y<=m;y++){
            if (dasie[x][y] && dasie2[x][y])cnt[x+y]++;
            else blok[x][y]=1;
        }
    }
    int q,a,b;
    cin >> q;
    while(q--){
        cin >> a >> b;
        if (!dasie[a][b] || !dasie2[a][b]){
            zab(a,b);
            blok[a][b]=1;
            cout << "1\n";
            continue;
        }
        if (cnt[a+b]==1){
            cout << "0\n";
            continue;
        }
        zab(a,b);
        blok[a][b]=1;
        cout << "1\n";
        /*for (int x=1;x<=n;x++){
            for (int y=1;y<=m;y++){
                cout << blok[x][y] << ' ';
            }
            cout << '\n';
        }
        cout << "\n\n";*/
    }
    return 0;
}

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