Submission #1167487

#TimeUsernameProblemLanguageResultExecution timeMemory
1167487PlayVoltzLibrary (JOI18_library)C++20
100 / 100
80 ms488 KiB
#include <bits/stdc++.h> #include "library.h" using namespace std; #define pb push_back void Solve(int n){ int prev=1; vector<vector<int> > graph(n+1); vector<int> vect(1, 1), temp; for (int i=2; i<=n; ++i){ temp.assign(n, 0); for (auto a:vect)temp[a-1]=1; temp[i-1]=1; int res=Query(temp); if (res>prev)vect.pb(i); else if (res==prev){ int low=-1, high=vect.size(); while (low+1<high){ int mid=(low+high)/2, c=1, f; temp.assign(n, 0); for (int j=mid; j<high; ++j)temp[vect[j]-1]=1; temp[i-1]=1; f=Query(temp); for (int j=mid; j<high-1; ++j){ bool got=0; for (auto a:graph[vect[j]])if (a==vect[j+1])got=1; c+=!got; } if (c==f)low=mid; else high=mid; } graph[vect[low]].pb(i); graph[i].pb(vect[low]); vect.pb(i); vector<bool> done(n+1, 0); vector<int> ooga; for (auto a:vect)if (graph[a].empty())ooga.pb(a), done[a]=1; for (auto a:vect)if (graph[a].size()==1&&!done[a]){ queue<int> q; q.push(a); while (q.size()){ int node=q.front(); q.pop(); done[node]=1; ooga.pb(node); for (auto num:graph[node])if (!done[num])q.push(num); } } vect=ooga; } else{ int low=-1, high=vect.size(); while (low+1<high){ int mid=(low+high)/2, c=1, f; temp.assign(n, 0); for (int j=mid; j<high; ++j)temp[vect[j]-1]=1; temp[i-1]=1; f=Query(temp); for (int j=mid; j<high-1; ++j){ bool got=0; for (auto a:graph[vect[j]])if (a==vect[j+1])got=1; c+=!got; } if (c>=f)low=mid; else high=mid; } vector<bool> del(n+1, 0); queue<int> q; q.push(vect[low]); while (q.size()){ int node=q.front(); q.pop(); del[node]=1; for (auto num:graph[node])if (!del[num])q.push(num); } vector<int> booga; for (auto a:vect)if (!del[a])booga.pb(a); graph[vect[low]].pb(i); graph[i].pb(vect[low]); low=-1, high=booga.size(); while (low+1<high){ int mid=(low+high)/2, c=1, f; temp.assign(n, 0); for (int j=mid; j<high; ++j)temp[booga[j]-1]=1; temp[i-1]=1; f=Query(temp); for (int j=mid; j<high-1; ++j){ bool got=0; for (auto a:graph[booga[j]])if (a==booga[j+1])got=1; c+=!got; } if (c>=f)low=mid; else high=mid; } graph[booga[low]].pb(i); graph[i].pb(booga[low]); vect.pb(i); vector<bool> done(n+1, 0); vector<int> ooga; for (auto a:vect)if (graph[a].empty())ooga.pb(a), done[a]=1; for (auto a:vect)if (graph[a].size()==1&&!done[a]){ queue<int> q; q.push(a); while (q.size()){ int node=q.front(); q.pop(); done[node]=1; ooga.pb(node); for (auto num:graph[node])if (!done[num])q.push(num); } } vect=ooga; } prev=res; } Answer(vect); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...