#include <iostream>
#include <vector>
#include <algorithm>
#include "longesttrip.h"
using namespace std;
int get(vector<int> A, vector<int> B){
int l = -1, r = A.size() - 1;
while (l + 1 < r){
int m = (l + r) / 2;
vector<int> v;
v.insert(v.end(), A.begin(), A.begin() + m + 1);
if (v.size() == 0){
cout<<l<<" "<<r<<" "<<m<<" "<<A.size()<<endl;
cout<<1 / 0;
}
if (are_connected(v, B))
r = m;
else
l = m;
}
return r;
}
vector<int> longest_trip(int n, int D){
vector<int> A = {0}, B, v;
for (int i=1;i<n;i++){
if (are_connected({A.back()}, {i})){
A.push_back(i);
if (B.size() > 0 and are_connected({i}, {B.back()})){
reverse(begin(B), end(B));
A.insert(A.end(), B.begin(), B.end());
B.clear();
}
}
else
B.push_back(i);
if (A.size() < B.size())
swap(A, B);
}
// cout<<"done1"<<endl;
if (B.size() == 0 or are_connected(A, B) == 0)
return A;
// cout<<"here"<<endl;
int l1 = get(A, B), l2 = get(B, {A[l1]});
if (l2 == 0)
swap(A, B), swap(l1, l2);
// cout<<"///////////////////////\n";
// for (int i : A)
// cout<<i<<' ';
// cout<<'\n';
// for (int i : B)
// cout<<i<<' ';
// cout<<'\n';
// cout<<l1<<" "<<l2<<endl;
// cout<<"///////////////////////\n";
if (l1){
for (int i=1;i<=l1;i++)
A.push_back(A[0]), A.erase(begin(A));
for (int i=1;i<=l2;i++)
B.push_back(B[0]), B.erase(begin(B));
}
else if (are_connected({A[0]}, {B.back()})){
reverse(begin(B), end(B));
}
else{
for (int i=1;i<=l2;i++)
B.push_back(B[0]), B.erase(begin(B));
}
for (int i : B)
A.insert(A.begin(), i);
return A;
}
