# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
282691 | 2020-08-24T18:45:40 Z | sckmd | Library (JOI18_library) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "library.h" #define MAX 1005 using namespace std; int Query(const std::vector<int>& M); void Answer(const std::vector<int>& res); vector <int> susedi[MAX]; int n; void go(int idx) { vector <int> all; for(int i = 0; i < n; i++) { if(i == idx)continue; if(find(susedi[i].begin(),susedi[i].end(),idx)!=susedi[i].end())continue; if(find(susedi[idx].begin(),sused[idx].end(),i)!=susedi[idx].end())continue; all.push_back(i); } vector <int> qq; for(int i = 0; i < n; i++)qq.push_back(0); int lo = 0,hi=all.size()-1,mid=lo+hi>>1,r=-1; while(lo <= hi) { for(int j = 0; j < n; j++)qq[j]=0; for(int j = lo; j <= mid; j++) { qq[all[j]]=1; } int qres = Query(qq); qq[idx]=1; int qres2 = Query(qq); if(qres2 <= qres)r=mid,hi=mid-1; else lo=mid+1; mid=lo+hi>>1; } if(r!=-1)susedi[idx].push_back(r),susedi[r].push_back(idx); } vector <int> resenje; void dfs(int v,int p) { resenje.push_back(v); for(auto x:susedi[v]) { if(x==p)continue; dfs(x,v); } } void Solve(int N) { n=N; for(int i = 0; i < n; i++) { if(!susedi[i].size())go(i); } for(int i = 0; i < n; i++) { if(susedi[i].size()==1){dfs(i,-1);break;} } Answer(resenje); }