답안 #788774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
788774 2023-07-20T15:09:59 Z anton Furniture (JOI20_furniture) C++17
5 / 100
5000 ms 184236 KB
#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;
        first_cols[j] = max(first_cols[j], i);
        first_lines[i] = max(first_lines[i], j);
        
        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(){
    }

    Map(vector<vector<bool>>& f){
        x=f.size()+1;
        y = f[0].size()+1;
        lines.resize(x);
        first_lines.resize(x, -1);
        cols.resize(y);
        first_cols.resize(y, -1);
        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;

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

        ok|=first_lines[i]>=j;
        ok|=first_cols[j]>=i;
        if(i>0){
            ok |=first_lines[i-1]>=j;
        }
        if(j>0){
            ok|= first_cols[j-1]>=i;
        }
        return ok;
    }

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

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

        ac.push_back(access);
        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));
        bool ok2= maps[1].try_insert(pii(m-b+1, a));

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

Compilation message

furniture.cpp: In constructor 'Map::Map(std::vector<std::vector<bool> >&)':
furniture.cpp:160:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for(int i = 0; i<ac.size(); i++){
      |                        ~^~~~~~~~~~
furniture.cpp: In function 'std::vector<std::vector<bool> > rotate(std::vector<std::vector<bool> >)':
furniture.cpp:209: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]
  209 |     for(int i = 0; i<a.size(); i++){
      |                    ~^~~~~~~~~
furniture.cpp:210: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]
  210 |         for(int j = 0; j<b.size(); j++){
      |                        ~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 11 ms 1332 KB Output is correct
3 Correct 18 ms 1536 KB Output is correct
4 Correct 25 ms 2544 KB Output is correct
5 Correct 27 ms 2636 KB Output is correct
6 Correct 31 ms 2784 KB Output is correct
7 Correct 28 ms 2764 KB Output is correct
8 Correct 27 ms 2756 KB Output is correct
9 Correct 27 ms 2772 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 11 ms 1332 KB Output is correct
3 Correct 18 ms 1536 KB Output is correct
4 Correct 25 ms 2544 KB Output is correct
5 Correct 27 ms 2636 KB Output is correct
6 Correct 31 ms 2784 KB Output is correct
7 Correct 28 ms 2764 KB Output is correct
8 Correct 27 ms 2756 KB Output is correct
9 Correct 27 ms 2772 KB Output is correct
10 Correct 88 ms 8392 KB Output is correct
11 Correct 18 ms 2060 KB Output is correct
12 Correct 2214 ms 92916 KB Output is correct
13 Correct 277 ms 42024 KB Output is correct
14 Execution timed out 5085 ms 184236 KB Time limit exceeded
15 Halted 0 ms 0 KB -