#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,i,j,k,s,t,x,y,z,w;
deque<ll> dq1,dq2;
vector<ll>v;
pair<ll,ll> p;
pair<ll,ll> inv(pair<ll,ll> p)
{
return {p.second,p.first};
}
pair<ll,ll> adj(vector<ll> a,vector<ll> b)
{
ll k=0;
if(a.size()<b.size())
{swap(a,b); k=1;}
if(a.size()==1&&b.size()==1)
return {a[0],b[0]};
vector<ll>c;
for(i=0;i<a.size()/2;i++)
c.push_back(a[i]);
if(are_connected(c,b))
{
if(k==1)
{
return inv(adj(c,b));
}
else
return adj(c,b);
}
else
{
c.clear();
for(i=a.size()/2;i<a.size();i++)
c.push_back(a[i]);
if(k==1)
{
return inv(adj(c,b));
}
else
return adj(c,b);
}
}
vector<ll> vectorize(deque<ll> d)
{
ll i;
vector<ll> v;
for(i=0;i<d.size();i++)
v.push_back(d[i]);
return v;
}
void combine()
{
for(auto x:dq2)
dq1.push_front(x);
dq2.clear();
}
void answer()
{
v.clear();
for(i=0;i<dq1.size();i++)
{
v.push_back(dq1[i]);
}
}
void init()
{
dq1.clear();
dq2.clear();
v.clear();
s=0;
t=0;
}
vector<ll> longest_trip(ll N, ll D)
{
init();
n=N;
dq1.push_back(0);
dq2.push_back(1);
for(i=2;i<n;i++)
{
if(are_connected({dq1[0]},{dq2[0]}))
{
combine();
dq2.push_back(i);
continue;
}
if(are_connected({dq1[0]},{i}))
{
dq1.push_front(i);
continue;
}
dq2.push_front(i);
}
if(dq1.size()<dq2.size())
swap(dq1,dq2);
if(!are_connected(vectorize(dq1),vectorize(dq2)))
{
answer();
return v;
}
if(dq2.size()==1)
{
if(are_connected({dq1[0]},{dq2[0]}))
{
dq1.push_front(dq2[0]);
}
else if(are_connected({dq1[dq1.size()-1]},{dq2[0]}))
{
dq1.push_back(dq2[0]);
}
else
{
for(i=0;i<dq1.size();i++)
{
v.push_back(dq1[i]);
}
x=adj(vectorize(dq1),vectorize(dq2)).first;
v.clear();
v.push_back(dq2[0]);
for(i=0;i<dq1.size();i++)
{
if(dq1[i]==x)
{
t=1;
}
if(t==1)
v.push_back(dq1[i]);
}
for(i=0;i<dq1.size();i++)
{
if(dq1[i]==x)
t=0;
if(t==1)
v.push_back(dq1[i]);
}
return v;
}
answer();
return v;
}
if(are_connected({dq1[0]},{dq2[0]}))
{
for(auto x:dq2)
dq1.push_front(x);
answer();
return v;
}
else if(are_connected({dq1[0]},{dq2[dq2.size()-1]}))
{
for(i=dq2.size()-1;i>=0;i--)
{
dq1.push_front(dq2[i]);
}
answer();
return v;
}
else if(are_connected({dq1[dq1.size()-1]},{dq2[0]}))
{
for(auto x:dq2)
dq1.push_back(x);
answer();
return v;
}
else if(are_connected({dq1[dq1.size()-1]},{dq2[dq2.size()-1]}))
{
for(i=dq2.size()-1;i>=0;i--)
{
dq1.push_back(dq2[i]);
}
answer();
return v;
}
else
{
p=adj(vectorize(dq1),vectorize(dq2));
x=p.first;
y=p.second;
t=0;
for(i=0;i<dq1.size();i++)
{
if(t==1)
{
v.push_back(dq1[i]);
}
if(dq1[i]==x)
t=1;
}
for(i=0;i<dq1.size();i++)
{
if(t==1)
v.push_back(dq1[i]);
if(dq1[i]==x)
t=0;
}
for(i=0;i<dq2.size();i++)
{
if(dq2[i]==x)
t=1;
if(t==1)
{
v.push_back(dq2[i]);
}
}
for(i=0;i<dq2.size();i++)
{
if(dq2[i]==x)
t=0;
if(t==1)
v.push_back(dq2[i]);
}
return v;
}
}
