#include "longesttrip.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> a[260];
vector<int> longest_trip(int N, int D)
{
srand(time(0));
vector<int> v(N);
for(int i=0; i<N; i++) v[i]=i;
random_shuffle(v.begin(),v.end());
vector<int> p1={v[0]},p2={v[1]};
int c=1,atb;
for(int i=2; i<N; i++){
if(c==0){
atb=are_connected(vector<int>(1,p1.back()),vector<int>(1,v[i]));
if(atb==1){
c=1;
p1.pb(v[i]);
}
else p2.pb(v[i]);
}else{
atb=are_connected(vector<int>(1,p1.back()),vector<int>(1,v[i]));
if(atb==1){
p1.pb(v[i]);
continue;
}
atb=are_connected(vector<int>(1,p2.back()),vector<int>(1,v[i]));
if(atb==1){
p2.pb(v[i]);
c=0;
continue;
}
for(int j=p2.size()-1; j>=0; j--) p1.pb(p2[j]);
p2.clear();
p2.pb(v[i]);
}
}
atb=are_connected(p1,p2);
if(atb==0){
if(p1.size()>p2.size()) return p1;
return p2;
}
vector<int> g1={p1[0]},g2={p2[0]};
if(p1.size()>1) g1.pb(p1.back());
if(p2.size()>1) g2.pb(p2.back());
atb=are_connected(g1,g2);
if(atb==1){
atb=are_connected(vector<int>(1,p1.back()),vector<int>(1,p2[0]));
if(atb==1){
for(int i=0; i<p2.size(); i++) p1.pb(p2[i]);
return p1;
}
atb=are_connected(vector<int>(1,p1.back()),vector<int>(1,p2.back()));
if(atb==1){
for(int i=p2.size()-1; i>=0; i--) p1.pb(p2[i]);
return p1;
}
atb=are_connected(vector<int>(1,p1[0]),vector<int>(1,p2.back()));
if(atb==1){
for(int i=0; i<p1.size(); i++) p2.pb(p1[i]);
return p2;
}
reverse(p1.begin(),p1.end());
for(int i=0; i<p2.size(); i++) p1.pb(p2[i]);
return p1;
}
int l=0,r=p1.size()-1,mid,s1p,s2p;
while(l<r){
mid=(l+r)/2;
vector<int> temp=vector<int>(p1.begin()+l,p1.begin()+mid+1);
atb=are_connected(temp,p2);
if(atb==0) l=mid+1;
else r=mid;
}
s1p=l;
l=0; r=p2.size();
while(l<r){
mid=(l+r)/2;
vector<int> temp=vector<int>(p2.begin()+l,p2.begin()+mid+1);
atb=are_connected(temp,p1);
if(atb==0) l=mid+1;
else r=mid;
}
s2p=l;
vector<int> rez;
for(int i=s1p-1; i>=0; i--) rez.pb(p1[i]);
for(int i=p1.size()-1; i>=s1p; i--) rez.pb(p1[i]);
for(int i=s2p; i>=0; i--) rez.pb(p2[i]);
for(int i=p2.size()-1; i>s2p; i--) rez.pb(p2[i]);
return rez;
}
