#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |