#include "park.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int place_a[1405];
int place_b[1405];
vector<int> tab;
vector<int> cur;
int parent[1405];
int depth[1405];
vector<int> a;
vector<int> b;
int binary_search_a(int start){
int l=-1;
int r=a.size()-1;
while(r-l>1){
int mid=(r+l)/2;
for (int i = 0; i <= mid; ++i)
{
place_a[a[i]]=0;
}
if(Ask(0,start,place_a)) l=mid;
else r=mid;
for (int i = 0; i <= mid; ++i)
{
place_a[a[i]]=1;
}
}
return r;
}
int binary_search_b(int start){
int l=-1;
int r=b.size();
while(r-l>1){
int mid=(r+l)/2;
for (int i = 0; i <= mid; ++i)
{
place_b[b[i]]=0;
}
if(Ask(0,start,place_b)) l=mid;
else r=mid;
for (int i = 0; i <= mid; ++i)
{
place_b[b[i]]=1;
}
}
return r;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int ans[1405];
int place[1405];
void daq(int start,int l,int r,vector<int> v){
if(l>r) return;
if(l==r){
ans[l]=v.back();
return;
}else if(r==1&&l==0){
ans[0]=start;
ans[1]=(v.back()==start ? v[0] : v[1]);
return;
}
int mid=uniform_int_distribution<int>(0,(int)v.size()-1)(rng);
while(v[mid]==0) mid=uniform_int_distribution<int>(0,(int)v.size()-1)(rng);
int y=v[mid];
vector<int> v1;
vector<int> v2;
for (int i = 0; i < v.size(); ++i)
{
if(v[i]==0||v[i]==y){
v1.push_back(v[i]);
continue;
}
place[v[i]]=0;
if(Ask(0,y,place)) v2.push_back(v[i]);
else v1.push_back(v[i]);
place[v[i]]=1;
}
daq(start,l,l+v1.size()-1,v1);
daq(start,l+v1.size(),r,v2);
}
void Detect(int T, int N){
if(N<=250){
int Place[255];
for (int i = 0; i < N; ++i)
{
for (int j = i+1; j < N; ++j)
{
for (int k = 0; k < N; ++k)
{
if(k==i||k==j) Place[k]=1;
else Place[k]=0;
}
if(Ask(i,j,Place)) Answer(i,j);
}
}
return;
}
n=N;
for (int i = 0; i < n; ++i) place_b[i]=place_a[i]=place[i]=1;
memset(depth,-1,sizeof depth);
memset(parent,-1,sizeof parent);
depth[0]=0;
a.push_back(0);
for (int i = 1; i < n; ++i)
{
b.push_back(i);
}
while(a.size()<n){
int x=b.back();
vector<int> cur;
cur.push_back(x);
b.pop_back();
int y=a[binary_search_a(x)];
int z=binary_search_b(x);
while(z<b.size()){
cur.push_back(b[z]);
vector<int> nab;
for (int i = 0; i < b.size(); ++i) if(i!=z) nab.push_back(b[i]);
b=nab;
z=binary_search_b(x);
}
cur.push_back(y);
/*cout <<y<<endl;
cout << "cur :";
for (auto u:cur) cout <<u<<" ";
cout <<endl;*/
daq(y,0,cur.size()-1,cur);
for (int i = 1; i < cur.size(); ++i)
{
a.push_back(ans[i]);
parent[ans[i]]=ans[i-1];
depth[ans[i]]=depth[ans[i-1]]+1;
}
/*cout << "b :";
for(auto u:b) cout <<u<<" ";
cout <<endl;*/
vector<pair<int,int>> inter;
for (int i = 0; i < a.size(); ++i) inter.push_back({depth[a[i]],a[i]});
sort(inter.begin(),inter.end(),greater<pair<int,int>>());
for (int i = 0; i < a.size(); ++i)
{
a[i]=inter[i].second;
}
/*cout << "a :";
for(auto u:a) cout <<u<<" ";
cout <<endl;*/
}
for (int i = 1; i < n; ++i)
{
int x=parent[i];
int y=i;
if(x>y) swap(x,y);
Answer(x,y);
}
return;
}
