Submission #788765

#	Time	Username	Problem	Language	Result	Execution time	Memory
788765		anton	Furniture (JOI20_furniture)	C++17	5 / 100	5062 ms	145092 KiB

furniture

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>

int n, m;

struct Map{
    int x, y;
    vector<vector<int>> ref;
    vector<bool> ac;
    vector<pii> pos_ref;
    vector<set<int>> lines;
    //vector<int> first_lines;
    vector<set<int>> cols;
    //vector<int> first_cols;

    vector<pii> neigs(pii pos){
        vector<pii> res;
        int i= pos.first;
        int j = pos.second;
        for(int di = -1; di<2; di++){
            for(int dj = -1; dj<2; dj++){
                if(di!=0|| dj!=0){
                    if(di+i<x && dj+j<y && di+i>=0 && dj+j>=0){
                        if(ref[di+i][dj+j]!=-1){
                            res.push_back(pii(di+i, dj+j));
                        }
                    }
                }
            }
        }
        return res;
    }

    vector<pii> spread(pii pos){
        int i = pos.first;
        int j = pos.second;

        vector<pii> r;

        auto it = lines[i].lower_bound(j);
        if(it != lines[i].begin()){
            r.push_back(pii(i, *(--it)));
        }
        it = cols[j].lower_bound(i);
        if(it!=cols[j].begin()){
            r.push_back(pii(*(--it), j));
        }
        if(i+1<x){
            it = lines[i+1].lower_bound(j);
            if(it != lines[i+1].begin() && lines[i+1].size()>0){
                r.push_back(pii( i+1, *(--it)));
            }
        }
        if(j+1<y){
            //cout<<"cols "<<j+1<<" "<<cols[j+1].size()<<endl;
            it =cols[j+1].lower_bound(i);
            if(it !=cols[j+1].begin() && cols[j+1].size()>0){
                r.push_back(pii(*(--it), j+1));
            }
        }
    

        return r;
    }

    vector<pii> rev_spread(pii pos){
        int i = pos.first;
        int j = pos.second;

        vector<pii> r;

        auto it = lines[i].upper_bound(j);
        if(it != lines[i].end()){
            r.push_back(pii(i,*it));
        }
        it = cols[j].upper_bound(i);
        if(it!=cols[j].end()){
            r.push_back(pii(*it, j));
        }
        if(i-1>=0){
            it = lines[i-1].upper_bound(j);
            if(it != lines[i-1].end()){
                r.push_back(pii(i-1, *(it)));
            }
        }
        if(j-1>=0){
            //cout<<"cols "<<j-1<<" "<<cols[j-1].size()<<endl;
            it =cols[j-1].upper_bound(i);
            if(it !=cols[j-1].end()){
                r.push_back(pii(*it, j-1));
            }
        }
        //cout<<"spread size"<<r.size()<<endl;
        return r;
    }

    void dfs(int i, int j){
        //cout<<"dfs "<<i<<" "<<j<<endl;
        ac[ref[i][j]] = true;
        
        for(auto e: neigs(pii(i, j))){
            if(ref[e.first][e.second]!=-1){
                //cout<<e.first<<" "<<e.second<<endl;
                //cout<<ref[e.first][e.second]<<endl;
                if(!ac[ref[e.first][e.second]]){
                    //cout<<"here"<<endl;
                    dfs(e.first, e.second);
                }
            }
        }
        //cout<<"none"<<endl;

        for(auto e: spread(pii(i, j))){
            //cout<<e.first<<" "<<e.second<<endl;
            if(!ac[ref[e.first][e.second]]){
                dfs(e.first, e.second);
            }
        }
    }

    Map(){};

    void display(){
        for(int i = 0; i<x; i++){
            for(int j = 0; j<y; j++){
                if(ref[i][j] ==-1){
                    //cout<<"O";
                }
                else{
                    if(ac[ref[i][j]]){
                        //cout<<"#";
                    }
                    else{
                        //cout<<"W";
                    }
                }
            }
            //cout<<endl;
        }
    }

    Map(vector<vector<bool>>& f){
        x=f.size()+1;
        y = f[0].size()+1;
        lines.resize(x);
        cols.resize(y);
        ref.resize(x, vector<int> (y, -1));
        for(int i = 0; i<x; i++){
            for(int j = 0; j<y; j++){
                if(i==0|| j==0){
                    ref[i][j] = ac.size();
                    ac.push_back(true);
                    pos_ref.push_back(pii(i, j));
                    lines[i].insert(j);
                    cols[j].insert(i);
                }
                else{
                    if(f[i-1][j-1]){     
                        ref[i][j] = ac.size(); 
                        ac.push_back(false);
                        pos_ref.push_back(pii(i, j));
                        lines[i].insert(j);
                        cols[j].insert(i);
                    }
                }
            }
        }

        for(int i = 0; i<ac.size(); i++){
            if(ac[i]){
                dfs(pos_ref[i].first, pos_ref[i].second);
            }
        }

        display();
    }

    bool try_insert(pii pos){
        int i = pos.first;
        int j = pos.second;
        bool ok = false;

        //cout<<"trying "<<pos.first<<" "<<pos.second<<endl;

        for(auto e: neigs(pos)){
            ok|= ac[ref[e.first][e.second]];
        }
        for(auto e: rev_spread(pos)){
            ok|= ac[ref[e.first][e.second]];
        }
        return ok;
    }

    void insert(pii pos){
        int i =pos.first;
        int j = pos.second;

        ref[i][j] = ac.size();

        ac.push_back(try_insert(pos));
        pos_ref.push_back(pii(i, j));
        lines[i].insert(j);
        cols[j].insert(i);

        if(ac.back()){
            dfs(i, j);
        }
    }
}maps[2]; 

vector<vector<bool>> rotate(vector<vector<bool>> a){
    vector<vector<bool>> b(a[0].size(), vector<bool>(a.size()));
    for(int i = 0; i<a.size(); i++){
        for(int j = 0; j<b.size(); j++){
            b[j][a.size()-i-1] = a[i][j];
        }
    }
    return b;
}

signed main(){
    cin>>n>>m;

    vector<vector<bool>> a(n, vector<bool> (m));

    for(int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            int c;
            cin>>c;

            a[i][j] = (c==1);
        }
    }

    auto b = rotate(a);
    auto c= rotate(rotate(b));
    maps[0]= Map(b);
    maps[1] = Map(c);

    maps[0].display();
    maps[1].display();

    int q;
    cin>>q;

    for(int i = 0; i<q; i++){
        int a, b;
        cin>>a>>b;

        bool ok =maps[0].try_insert(pii(b, n-a+1));
        ok&= maps[1].try_insert(pii(m-b+1, a));

        if(ok){
            cout<<0<<endl;
        }
        else{
            cout<<1<<endl;
            maps[0].insert(pii(b, n-a+1));
            maps[1].insert(pii(m-b+1, a));
        }
        
    }
}

Compilation message (stderr)

furniture.cpp: In constructor 'Map::Map(std::vector<std::vector<bool> >&)':
furniture.cpp:172:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |         for(int i = 0; i<ac.size(); i++){
      |                        ~^~~~~~~~~~
furniture.cpp: In member function 'bool Map::try_insert(std::pair<long long int, long long int>)':
furniture.cpp:182:13: warning: unused variable 'i' [-Wunused-variable]
  182 |         int i = pos.first;
      |             ^
furniture.cpp:183:13: warning: unused variable 'j' [-Wunused-variable]
  183 |         int j = pos.second;
      |             ^
furniture.cpp: In function 'std::vector<std::vector<bool> > rotate(std::vector<std::vector<bool> >)':
furniture.cpp:216:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     for(int i = 0; i<a.size(); i++){
      |                    ~^~~~~~~~~
furniture.cpp:217:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |         for(int j = 0; j<b.size(); j++){
      |                        ~^~~~~~~~~

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