Submission #772629

#	Time	Username	Problem	Language	Result	Execution time	Memory
772629		gagik_2007	Furniture (JOI20_furniture)	C++17	0 / 100	5 ms	852 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];
bool used[N][N];
set<int>dt[N];
set<int>dc[N];
int urc[N], urt[N];
int blc[N], blt[N];

void kpcruBL(int i, int j){
    bl[i][j]=true;
    a[i][j]=true;
    for(int jj=1;jj<=j;jj++){
        a[i][jj]=true;
        bl[i][jj]=true;
    }
    for(int ii=i;ii<n;ii++){
        a[ii][j]=true;
        bl[ii][j]=true;
    }
}

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

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);
            }
        }
    }
}

void gnaBL(int i, int j){
    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);
            }
        }
    }
}

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(urka&&blka)return 0;
    if(urka){
        gnaUR(i,j);
    }
    if(blka){
        gnaBL(i,j);
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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=1;j<=m;j++){
            if(b[i][j])query(i,j);
        }
    }
    // for(int i=1;i<=n;i++){
    //     urt[i]=m+10;
    //     blt[i]=-10;
    // }
    // for(int j=1;j<=m;j++){
    //     blc[j]=n+10;
    //     urc[j]=-10;
    // }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         if(ur[i][j]){
    //             urc[j]=max(urc[j],i);
    //             urt[i]=min(urt[i],j);
    //         }
    //         if(bl[i][j]){
    //             blc[j]=min(blc[j],i);
    //             blt[i]=max(blt[i],j);
    //         }
    //     }
    // }
    // urt[0]=0;
    // urc[m+1]=n;
    // for(int i=1;i<=n;i++){
    //     auto it=dt[i].lower_bound(urt[i-1]-1);
    //     urt[i]=m+10;
    //     if(it!=dt[i].end())urt[i]=*it;
    //     for(int j=m;j>=1;j--){
    //         auto itt=dc[j].upper_bound(urc[j+1]+1);
    //         urc[j]=-10;
    //         if(itt!=dc[j].begin())urc[j]=*(--itt);
    //         if(urt[i]<=j||urc[j]>=i){
    //             a[i][j]=true;
    //             ur[i][j]=true;
    //             dt[i].insert(j);
    //             dc[j].insert(i);
    //         }
    //     }
    // }
    // blt[n+1]=m;
    // blc[0]=0;
    // for(int i=n;i>=1;i--){
    //     auto it=dt[i].upper_bound(blt[i+1]+1);
    //     blt[i]=-10;
    //     if(it!=dt[i].begin())blt[i]=*(--it);
    //     // cout<<"i - "<<i<<": "<<blt[i]<<endl;
    //     for(int j=1;j<=m;j++){
    //         // cout<<"dc: ";
    //         // for(int x:dc[j]){
    //         //     cout<<x<<" ";
    //         // }
    //         // cout<<endl;
    //         auto itt=dc[j].lower_bound(blc[j-1]-1);
    //         blc[j]=n+10;
    //         if(itt!=dc[j].end())blc[j]=*itt;
    //         // cout<<"j - "<<j<<": "<<blc[j]<<endl;
    //         if(blt[i]>=j||blc[j]<=i){
    //             a[i][j]=true;
    //             // cout<<i<<", "<<j<<": "<<blt[i]<<" "<<blc[j]<<endl;
    //             bl[i][j]=true;
    //             dt[i].insert(j);
    //             dc[j].insert(i);
    //         }
    //     }
    // }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<a[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;
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<ur[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;
    cin>>k;
    for(int c=0;c<k;c++){
        int i,j;
        cin>>i>>j;
        cout<<query(i,j)<<endl;
    // assert(false);
    }
}

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