#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int cnt=0;
int n;
map<int, map<int,int>> mp;
bool query1(int a, int b) {
if(mp[a][b]!=0)return mp[a][b]-1;
int c=are_connected({a}, {b});
mp[a][b]=c+1;
mp[b][a]=c+1;
cnt++;
return c;
}
bool query2(int a, int b) {
for(int j = 0;j<n;j++) {
if(a==j or j==b)continue;
if(mp[a][j]==1 and mp[j][b]==1) {
mp[a][b]=2;
mp[b][a]=2;
return 1;
}
}
return query1(a,b);
}
vector<int> longest_trip(int N, int D)
{
n=N;
cnt=0;
mp.clear();
srand(time(NULL));
vector<int> id(N);
iota(id.begin(), id.end(), 0);
random_shuffle(id.begin(), id.end());
vector<int> t[2];
t[0].push_back(id[0]);
t[1].push_back(id[1]);
bool connected=1;
for(int ii = 2;ii<N;ii++) {
int i=id[ii];
if(t[0].size() < t[1].size())swap(t[0], t[1]);
if(t[1].size()>0 and rand()%2) {
swap(t[0], t[1]);
}
if(query2(i, t[0].back())) {
t[0].push_back(i);
connected=1;
}
else if(connected==false or query2(i, t[1].back())) {
t[1].push_back(i);
}
else {
connected=1;
while(t[1].size()) {
t[0].push_back(t[1].back());
t[1].pop_back();
}
t[1].push_back(i);
}
}
if(t[0].size()<t[1].size())swap(t[0], t[1]);
if(t[1].size()==0)return t[0];
if(query2(t[0][0], t[1].back())) {
reverse(t[0].begin(), t[0].end());
while(t[1].size()) {
t[0].push_back(t[1].back());
t[1].pop_back();
}
return t[0];
}
if(query2(t[0][0], t[1][0])) {
reverse(t[0].begin(), t[0].end());
reverse(t[1].begin(), t[1].end());
while(t[1].size()) {
t[0].push_back(t[1].back());
t[1].pop_back();
}
return t[0];
}
if(query2(t[0].back(), t[1][0])) {
reverse(t[1].begin(), t[1].end());
while(t[1].size()) {
t[0].push_back(t[1].back());
t[1].pop_back();
}
return t[0];
}
if(are_connected(t[0], t[1])==false)return t[0];
int lo = 0, hi = t[0].size()-1;
int res=hi;
while(lo <= hi) {
int mid=(lo+hi)/2;
vector<int> tmp;
for(int j = 0;j<=mid;j++)tmp.push_back(t[0][j]);
if(are_connected(tmp, t[1])) {
res=mid;
hi=mid-1;
}
else{
lo=mid+1;
}
}
lo=0, hi=t[1].size()-1;
int res2=hi;
while(lo <= hi) {
int mid=(lo+hi)/2;
vector<int> tmp;
for(int j = 0;j<=mid;j++)tmp.push_back(t[1][j]);
if(are_connected(tmp, {t[0][res]})) {
res2=mid;
hi=mid-1;
}
else{
lo=mid+1;
}
}
vector<int> ans;
for(int j = res+1;j<t[0].size();j++) {
ans.push_back(t[0][j]);
}
for(int j = 0;j<=res;j++)ans.push_back(t[0][j]);
for(int j = res2;j<t[1].size();j++)ans.push_back(t[1][j]);
for(int j = 0;j<res2;j++)ans.push_back(t[1][j]);
return ans;
}
