제출 #788765

#제출 시각아이디문제언어결과실행 시간메모리
788765antonFurniture (JOI20_furniture)C++17
5 / 100
5062 ms145092 KiB
#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)); } } }

컴파일 시 표준 에러 (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++){
      |                        ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...