Submission #773215

#	Time	Username	Problem	Language	Result	Execution time	Memory
773215		gagik_2007	Furniture (JOI20_furniture)	C++17	100 / 100	2504 ms	16016 KiB

furniture

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=1007;
const ll LG=25;
ll n,m,k;
bool a[N][N];
bool b[N][N];
bool bl[N][N];
bool ur[N][N];

void gnaBL(int i, int j);

void kpcruBL(int i, int j){
    // if(i==97&&j==33){
    //     cout<<"\n\n\n\nHAAAAAAAAAAAA!!!\n\n\n\n";
    // }
    bl[i][j]=true;
    a[i][j]=true;
    for(int jj=1;jj<=j;jj++){
        if(!bl[i][jj]){
            a[i][jj]=true;
            bl[i][jj]=true;
            gnaBL(i,jj);
        }
    }
    for(int ii=i;ii<=n;ii++){
        if(!bl[ii][j]){
            a[ii][j]=true;
            bl[ii][j]=true;
            gnaBL(ii,j);
        }
    }
}

void gnaBL(int i, int j){
    // cout<<i<<" "<<j<<endl;
    kpcruBL(i,j);
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)&&!bl[ii][jj]){
                gnaBL(ii,jj);
            }
        }
    }
}

void gnaUR(int i, int j);

void kpcruUR(int i, int j){
    ur[i][j]=true;
    a[i][j]=true;
    for(int jj=j;jj<=m;jj++){
        if(!ur[i][jj]){
            a[i][jj]=true;
            ur[i][jj]=true;
            gnaUR(i,jj);
        }
    }
    for(int ii=1;ii<=i;ii++){
        if(!ur[ii][j]){
            a[ii][j]=true;
            ur[ii][j]=true;
            gnaUR(ii,j);
        }
    }
}

void gnaUR(int i, int j){
    kpcruUR(i,j);
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)&&!ur[ii][jj]){
                gnaUR(ii,jj);
            }
        }
    }
}

int query(int i, int j){
    
    bool urka=false;
    bool blka=false;
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)){
                if(ur[ii][jj])urka=true;
                if(bl[ii][jj])blka=true;
            }
        }
    }
    // if(i==97&&j==33){
    //     cout<<urka<<" "<<blka<<endl;
    //     cout<<"\n\n\n\nHAAAAAAAAAAAA!!!\n\n\n\n";
    // }
    if(urka&&blka)return 0;
    if(urka){
        // cout<<"KPAV UR-in\n";
        gnaUR(i,j);
        // cout<<"TAZA UR:\n";
        // for(int i=0;i<=n+1;i++){
        //     for(int j=0;j<=m+1;j++){
        //         cout<<ur[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        // cout<<endl;
    }
    if(blka){
        // cout<<"KPAV BL-in\n";
        gnaBL(i,j);
        // cout<<"TAZA BL:\n";
        // for(int i=0;i<=n+1;i++){
        //     for(int j=0;j<=m+1;j++){
        //         cout<<bl[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        // cout<<endl;
    }
    a[i][j]=true;
    return 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("output.txt","w",stdout);
    cin>>n>>m;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            if(i==0||i==n+1||j==0||j==m+1){
                a[i][j]=true;
                if(i==0||j==m+1)ur[i][j]=true;
                else bl[i][j]=true;
                continue;
            }
            cin>>b[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            if(b[i][j])query(i,j);
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            if(b[i][j])query(i,j);
        }
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<a[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    cin>>k;
    for(int c=0;c<k;c++){
        int i,j;
        cin>>i>>j;
        cout<<query(i,j)<<endl;
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<ur[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<bl[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
}

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