oj.uz

답안 #788765

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
788765 2023-07-20T14:56:30 Z anton Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 145092 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;
        
        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

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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 15 ms 1276 KB Output is correct
3 Correct 24 ms 1548 KB Output is correct
4 Correct 33 ms 2472 KB Output is correct
5 Correct 47 ms 2568 KB Output is correct
6 Correct 45 ms 2728 KB Output is correct
7 Correct 37 ms 2756 KB Output is correct
8 Correct 42 ms 2864 KB Output is correct
9 Correct 35 ms 2772 KB Output is correct

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 15 ms 1276 KB Output is correct
3 Correct 24 ms 1548 KB Output is correct
4 Correct 33 ms 2472 KB Output is correct
5 Correct 47 ms 2568 KB Output is correct
6 Correct 45 ms 2728 KB Output is correct
7 Correct 37 ms 2756 KB Output is correct
8 Correct 42 ms 2864 KB Output is correct
9 Correct 35 ms 2772 KB Output is correct
10 Correct 116 ms 8448 KB Output is correct
11 Correct 25 ms 1956 KB Output is correct
12 Correct 3222 ms 96660 KB Output is correct
13 Correct 337 ms 43592 KB Output is correct
14 Execution timed out 5062 ms 145092 KB Time limit exceeded
15 Halted 0 ms 0 KB -