제출 #937805

#제출 시각아이디문제언어결과실행 시간메모리
937805pcc카멜레온의 사랑 (JOI20_chameleon)C++14
100 / 100
46 ms852 KiB
#include "chameleon.h" #include <vector> #include <bits/stdc++.h> #define pii pair<int,int> #define fs first #define sc second using namespace std; const int mxn = 1010; vector<int> bigraph[mxn]; bitset<mxn> mat[mxn]; int N; namespace BUILD{ int deg[mxn]; vector<int> v[2]; void get_edge(int now){ int l = 0,r = v[0].size()-1; while(l != r){ int mid = (l+r)>>1; vector<int> vv = {now}; for(int i = 0;i<=mid;i++){ if(mat[now][v[0][i]])continue; vv.push_back(v[0][i]); } if(Query(vv) != vv.size())r = mid; else l = mid+1; } //cout<<now<<":"<<v[0][l]<<endl; mat[now][v[0][l]] = mat[v[0][l]][now] = true; bigraph[now].push_back(v[0][l]); bigraph[v[0][l]].push_back(now); deg[now]++,deg[v[0][l]]++; return; } bool done(int now){ vector<int> vv; for(auto &i:v[0]){ if(mat[now][i])continue; vv.push_back(i); } vv.push_back(now); if(Query(vv) != vv.size())return false; else return true; } void GO(){ vector<int> rest; for(int i = 1;i<=N*2;i++)rest.push_back(i); while(!rest.empty()){ v[0].clear();v[1].clear(); for(auto &i:rest){ if(v[0].empty())v[0].push_back(i); else{ v[0].push_back(i); if(Query(v[0]) != v[0].size()){ v[0].pop_back(); v[1].push_back(i); } } } //cout<<"---"<<endl; //for(auto &i:v[0])cout<<i<<',';cout<<endl; //for(auto &i:v[1])cout<<i<<',';cout<<endl; rest.clear(); for(auto &i:v[1]){ do{ get_edge(i); }while(deg[i]<3&&!done(i)); } rest = v[1]; } return; } int col[mxn]; void dfs(int now,int c){ col[now] = c; for(auto nxt:bigraph[now]){ if(col[nxt] == -1)dfs(nxt,c^1); } return; } void COLOR(){ memset(col,-1,sizeof(col)); for(int i = 1;i<=N*2;i++){ if(col[i] == -1)dfs(i,1); } return; } void PRINT(){ for(int i = 1;i<=N*2;i++){ cout<<i<<":";for(auto &j:bigraph[i])cout<<j<<',';cout<<endl; } cout<<endl; for(int i = 1;i<=N*2;i++)cout<<col[i];cout<<endl; return; } } namespace GETANS{ vector<pii> ans; void GO(){ for(int i = 1;i<=N*2;i++){ if(bigraph[i].size()==1)continue; assert(bigraph[i].size()==3); vector<int> nei = bigraph[i]; vector<int> v[2] = {{i,bigraph[i][0],bigraph[i][1]},{i,bigraph[i][0],bigraph[i][2]}}; int tmp[2] = {Query(v[0]),Query(v[1])}; int now = i; if(tmp[0] == 1)mat[now][nei[2]] = mat[nei[2]][now] = 0; else if(tmp[1] == 1)mat[now][nei[1]] = mat[nei[1]][now] = 0; else mat[now][nei[0]] = mat[nei[0]][now] = 0; } for(int i = 1;i<=N*2;i++){ for(int j = i+1;j<=N*2;j++){ if(mat[i][j])ans.push_back({i,j}); } } for(auto &i:ans){ Answer(i.fs,i.sc); } return; } } void Solve(int NN) { N = NN; //cout<<"HI"<<":"<<N<<endl; BUILD::GO(); //cout<<"HI"<<":"<<N<<endl; BUILD::COLOR(); //BUILD::PRINT(); //cout<<"HI"<<":"<<N<<endl; GETANS::GO(); //cout<<"HI"<<":"<<N<<endl; }

컴파일 시 표준 에러 (stderr) 메시지

chameleon.cpp: In function 'void BUILD::get_edge(int)':
chameleon.cpp:30:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    if(Query(vv) != vv.size())r = mid;
      |       ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'bool BUILD::done(int)':
chameleon.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   if(Query(vv) != vv.size())return false;
      |      ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'void BUILD::GO()':
chameleon.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |      if(Query(v[0]) != v[0].size()){
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~
chameleon.cpp: In function 'void BUILD::PRINT()':
chameleon.cpp:101:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  101 |   for(int i = 1;i<=N*2;i++)cout<<col[i];cout<<endl;
      |   ^~~
chameleon.cpp:101:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  101 |   for(int i = 1;i<=N*2;i++)cout<<col[i];cout<<endl;
      |                                         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...