oj.uz

Submission #773215

# Submission time Handle Problem Language Result Execution time Memory
773215 2023-07-04T16:56:06 Z gagik_2007 Furniture (JOI20_furniture) C++17
100 / 100
 2504 ms 16016 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 5 ms 724 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 11 ms 724 KB Output is correct
5 Correct 12 ms 844 KB Output is correct
6 Correct 14 ms 852 KB Output is correct
7 Correct 15 ms 840 KB Output is correct
8 Correct 14 ms 844 KB Output is correct
9 Correct 14 ms 808 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 5 ms 724 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 11 ms 724 KB Output is correct
5 Correct 12 ms 844 KB Output is correct
6 Correct 14 ms 852 KB Output is correct
7 Correct 15 ms 840 KB Output is correct
8 Correct 14 ms 844 KB Output is correct
9 Correct 14 ms 808 KB Output is correct
10 Correct 63 ms 852 KB Output is correct
11 Correct 9 ms 644 KB Output is correct
12 Correct 929 ms 9480 KB Output is correct
13 Correct 162 ms 5932 KB Output is correct
14 Correct 1808 ms 13968 KB Output is correct
15 Correct 1799 ms 13856 KB Output is correct
16 Correct 2059 ms 14792 KB Output is correct
17 Correct 2243 ms 15448 KB Output is correct
18 Correct 2134 ms 16000 KB Output is correct
19 Correct 2502 ms 15852 KB Output is correct
20 Correct 2504 ms 16016 KB Output is correct
21 Correct 2331 ms 15992 KB Output is correct