제출 #937551

#제출 시각아이디문제언어결과실행 시간메모리
937551guagua0407카멜레온의 사랑 (JOI20_chameleon)C++17
0 / 100
35 ms4784 KiB
#include "chameleon.h" #include<bits/stdc++.h> namespace { using namespace std; #define all(x) x.begin(),x.end() map<vector<int>,int> mp; int n; vector<int> cnt; vector<bool> visited; mt19937 rng(time(NULL)); int query(vector<int> vec){ sort(vec.begin(),vec.end()); if(mp.find(vec)!=mp.end()) return mp[vec]; else{ /*for(auto v:vec){ cout<<v+1<<' '; } cout<<'\n';*/ int x=Query(vec); mp[vec]=x; return x; } } void sir(vector<int> vec){ sort(all(vec)); if(mp.find(vec)==mp.end()){ mp[vec]=-1; } } bool comp(int a,int b){ return cnt[a]>cnt[b]; } } // namespace void Solve(int N) { using namespace std; n=N; n*=2; /*vector<int> res(1<<n); for(int i=0;i<(1<<n);i++){ vector<int> vec; for(int j=0;j<n;j++){ if(i&(1<<j)){ vec.push_back(j+1); } } res[i]=Query(vec); }*/ vector<vector<int>> one(n); vector<bool> two(n); visited.resize(n); cnt.resize(n); for(int i=0;i<n;i++){ vector<int> p(n); for(int j=0;j<n;j++){ p[j]=j; } sort(all(p),comp); for(int k=0;k<n;k++){ int j=p[k]; if(j==i or j/(n/2)==i/(n/2)) continue; if(query({i+1,j+1})==1) one[i].push_back(j); if((int)one[i].size()==3) break; } for(int j=0;j<n;j++){ if(j==i) continue; sir({i,j}); if(query({i,j})!=1) cnt[j]++; } if((int)one[i].size()==1){ two[i]=true; visited[one[i][0]]=true; } } vector<bool> used(n); for(int i=0;i<n;i++){ if(used[i]) continue; if(two[i]){ Answer(i+1,one[i][0]+1); used[i]=used[one[i][0]]=true; continue; } int a=one[i][0]; int b=one[i][1]; int c=one[i][2]; if(two[a]){ Answer(i+1,a+1); used[i]=used[a]=true; continue; } else if(two[b]){ Answer(i+1,b+1); used[i]=used[b]=true; continue; } else if(two[c]){ Answer(i+1,c+1); used[i]=used[c]=true; continue; } else{ if(one[a][0]==i or one[a][1]==i){ Answer(i+1,a+1); used[i]=used[a]=true; } if(one[b][0]==i or one[b][1]==i){ Answer(i+1,b+1); used[i]=used[b]=true; } else{ Answer(i+1,c+1); used[i]=used[c]=true; } } } /*return ; for(int i=0;i<(1<<n);i++){ vector<int> same(n); vector<int> prv(n,-1); for(int j=0;j<n;j++){ if(two[j]) continue; if(i&(1<<j)){ same[j]=1; prv[one[j][0]]=j; } else{ same[j]=0; prv[one[j][1]]=j; } } bool tf=true; for(int j=0;j<n;j++){ if(two[j]) continue; int x=prv[j]; if(x==-1){ tf=false; break; } int y=one[j][same[j]]; if(y==-1){ tf=false; break; } int ans=res[(1<<x)|(1<<j)|(1<<y)]; if(ans!=1){ tf=false; break; } } if(tf){ vector<bool> used(n); for(int j=0;j<n;j++){ if(used[j]) continue; int x=one[j][same[j]]; assert(!used[x]); Answer(j+1,x+1); used[j]=used[x]=true; } } }*/ }
#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...