Submission #623023

#	Time	Username	Problem	Language	Result	Execution time	Memory
623023		Mahdi	Furniture (JOI20_furniture)	C++17	100 / 100	1075 ms	52980 KiB

furniture

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=1e3+5;
int n, m, q;
bool a[N][N], b[N][N], x[N][N], y[N][N], c[N][N];

bool add(int i, int j){
    if(!x[i+1][j-1] && !y[i-1][j+1])
        return 0;
    set<pii>s, t;
    vector<pii>v;
    v.push_back({i, j});
    if(a[i][j]){
        a[i][j]=0;
        for(int k=0;k<v.size();++k){
            i=v[k].F, j=v[k].S;
            if(x[i][j])
                s.insert({-i, j});
            if(y[i][j])
                t.insert({i, -j});
            if(a[i+1][j] && !a[i+1][j-1]){
                v.push_back({i+1, j});
                a[i+1][j]=0;
            }
            if(a[i][j+1] && !a[i-1][j+1]){
                v.push_back({i, j+1});
                a[i][j+1]=0;
            }
        }
    }
    v.resize(1);
    if(b[v[0].F][v[0].S]){
        b[v[0].F][v[0].S]=0;
        for(int k=0;k<v.size();++k){
            i=v[k].F, j=v[k].S;
            if(x[i][j])
                s.insert({-i, j});
            if(y[i][j])
                t.insert({i, -j});
            if(b[i-1][j] && !b[i-1][j+1]){
                v.push_back({i-1, j});
                b[i-1][j]=0;
            }
            if(b[i][j-1] && !b[i+1][j-1]){
                v.push_back({i, j-1});
                b[i][j-1]=0;
            }
        }
    }
    while(!s.empty()){
        i=-s.begin()->F;
        j=s.begin()->S;
        s.erase(s.begin());
        if(!x[i+1][j] && !x[i][j-1] && (!a[i][j] || !b[i][j])){
            x[i][j]=0;
            if(x[i-1][j])
                s.insert({-i+1, j});
            if(x[i][j+1])
                s.insert({-i, j+1});
        }
    }
    while(!t.empty()){
        i=t.begin()->F;
        j=-t.begin()->S;
        t.erase(t.begin());
        if(!y[i-1][j] && !y[i][j+1] && (!a[i][j] || !b[i][j])){
            y[i][j]=0;
            if(y[i+1][j])
                t.insert({i+1, -j});
            if(y[i][j-1])
                t.insert({i, -j+1});
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            a[i][j]=b[i][j]=x[i][j]=y[i][j]=1;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>c[i][j];
            if(c[i][j])
                add(i, j);
        }
    }
    cin>>q;
    while(q--){
        int i, j;
        cin>>i>>j;
        cout<<add(i, j)<<'\n';
    }
}

Compilation message (stderr)

furniture.cpp: In function 'bool add(int, int)':
furniture.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int k=0;k<v.size();++k){
      |                     ~^~~~~~~~~
furniture.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int k=0;k<v.size();++k){
      |                     ~^~~~~~~~~

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