#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const int N = 1000 * 1000 + 7;
bool SQ(int a, int b)
{
vector<int> v1 = {a}, v2 = {b};
return are_connected(v1, v2);
}
void J(vector<int> &a, vector<int> &b)
{
for(int i = 0; i < (int)b.size(); ++i)
a.pb(b[i]);
b.clear();
}
void R(vector<int> &a, int r)
{
vector<int> nw;
for(int i = r; i < (int)a.size(); ++i)
nw.pb(a[i]);
for(int i = 0; i < r; ++i)
nw.pb(a[i]);
a = nw;
}
void Merge(vector<int> &a, vector<int> &b, bool xd)
{
if(!xd && SQ(a.back(), b.back()))
{
reverse(b.begin(), b.end());
J(a, b);
return;
}
if(SQ(a.back(), b[0]))
{
J(a, b);
return;
}
if(SQ(a[0], b.back()))
{
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
J(a, b);
return;
}
int p, s, k;
vector<int> q1, qd;
p = 0, k = (int)a.size();
while(p < k)
{
s = (p + k) / 2;
q1.clear();
for(int i = 0; i <= s; ++i)
q1.pb(a[i]);
if(are_connected(q1, b))
k = s;
else
p = s + 1;
}
if(p == (int)a.size()) return;
R(a, p);
qd = {a[0]};
p = 0, k = (int)b.size();
while(p < k)
{
s = (p + k) / 2;
q1.clear();
for(int i = 0; i <= s; ++i)
q1.pb(b[i]);
if(are_connected(q1, qd))
k = s;
else
p = s + 1;
}
R(b, p);
reverse(a.begin(), a.end());
J(a, b);
}
vector<int> longest_trip(int _N, int _X_D)
{
int n = _N;
vector<int> l1, l2;
bool xd = true;
l1.pb(0);
for(int i = 1; i < n; ++i)
{
if(l1.size() < l2.size()) swap(l1, l2);
if(SQ(i, l1.back()))
{
l1.pb(i);
if(l2.size() != 0) xd = false;
continue;
}
if(xd || SQ(i, l2.back()))
{
l2.pb(i);
xd = true;
continue;
}
reverse(l2.begin(), l2.end());
if((int)l2.size() > 0) xd = false;
else xd = true;
J(l1, l2);
l2.pb(i);
}
if(n == 1) return l1;
if(l1.size() < l2.size())
swap(l1, l2);
if(l2.size() == 0)
return l1;
Merge(l1, l2, xd);
return l1;
}
