#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> longest_trip(int N, int D)
{
vector<int> d[2];
d[0]={0}, d[1]={1};
int idx;
bool just_connect_mid=0, no_connect_top=0;
for (int i=2; i<N; i++)
{
if (no_connect_top)
{
if (are_connected(vector<int> {d[0].back()}, vector<int> {i}))
{
d[0].push_back(i);
}
else
{
d[1].push_back(i);
}
no_connect_top=0;
}
else if (just_connect_mid)
{
if (are_connected(vector<int> {d[1].back()}, vector<int> {i}))
{
d[1].push_back(i);
}
else
{
vector<int> tmp;
while (d[0].size()>idx) tmp.push_back(d[0].back()), d[0].pop_back();
d[0].push_back(i);
while (!tmp.empty()) d[0].push_back(tmp.back()), tmp.pop_back();
}
just_connect_mid=0;
}
else
{
if (are_connected(vector<int> {d[0].back()}, vector<int> {i}))
{
d[0].push_back(i);
}
else if (are_connected(vector<int> {d[1].back()}, vector<int> {i}))
{
no_connect_top=1;
d[1].push_back(i);
}
else
{
just_connect_mid=1;
idx=d[0].size();
while (!d[1].empty()) d[0].push_back(d[1].back()), d[1].pop_back();
d[1].push_back(i);
}
}
}
if (!are_connected(d[0], d[1]))
{
if (d[0].size()>d[1].size()) return d[0];
else return d[1];
}
if (are_connected(vector<int> {d[0].front()}, vector<int> {d[1].front()}))
{
reverse(d[0].begin(), d[0].end());
for (auto x:d[1]) d[0].push_back(x);
return d[0];
}
if (are_connected(vector<int> {d[0].front()}, vector<int> {d[1].back()}))
{
for (auto x:d[0]) d[1].push_back(x);
return d[1];
}
if (are_connected(vector<int> {d[0].back()}, vector<int> {d[1].front()}))
{
for (auto x:d[1]) d[0].push_back(x);
return d[0];
}
if (are_connected(vector<int> {d[0].back()}, vector<int> {d[1].back()}))
{
reverse(d[1].begin(), d[1].end());
for (auto x:d[1]) d[0].push_back(x);
return d[0];
}
int l=0, r=d[0].size()-1, p0, p1;
while (l<r)
{
int md=(l+r)/2;
vector<int> a;
for (int i=0; i<=md; i++) a.push_back(d[0][i]);
if (are_connected(a, d[1])) r=md;
else l=md+1;
}
p0=l;
l=0, r=d[1].size()-1;
while (l<r)
{
int md=(l+r)/2;
vector<int> a;
for (int i=0; i<=md; i++) a.push_back(d[1][i]);
if (are_connected(a, vector<int> {d[0][p0]})) r=md;
else l=md+1;
}
p1=l;
vector<int> res;
for (int i=p0+1; i<d[0].size(); i++) res.push_back(d[0][i]);
for (int i=0; i<=p0; i++) res.push_back(d[0][i]);
for (int i=p1; i<d[1].size(); i++) res.push_back(d[1][i]);
for (int i=0; i<p1; i++) res.push_back(d[1][i]);
return res;
}
