#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> longest_trip(int N, int D)
{
list <int> l1(0),l2(0);
l1.push_back(0);
l2.push_back(1);
bool prems = false;
for (int i(2); i < N; i++) {
if (are_connected({i},{l1.back()})) {
l1.push_back(i);
prems = false;
}
else if (prems || are_connected({i},{l2.front()})) {
l2.push_front(i);
prems = true;
}
else {
l1.insert(l1.end(), l2.begin(), l2.end());
l2.clear();
l2.push_back(i);
prems = false;
}
}
vector< int > v1, v2;
while (!l1.empty()) {
v1.push_back(l1.front());
l1.pop_front();
}
while (!l2.empty()) {
v2.push_back(l2.front());
l2.pop_front();
}
if (v2.empty()) return v1;
if (!are_connected(v1, v2)) {
if (v1.size() > v2.size()) return v1;
return v2;
}
/*for (int x : v1) cout << x << " ";
cout << '\n';
for (int x : v2) cout << x << " ";
cout << '\n';*/
if (int (v1.size()) != 1 && !are_connected({v1[0]}, {v1.back()})) {
if (are_connected({v2[0]}, {v1.back()})) {
v1.insert(v1.end(), v2.begin(), v2.end());
}
else {
v1.insert(v1.begin(), v2.rbegin(), v2.rend());
}
return v1;
}
if ( int(v2.size()) != 1 && !are_connected({v2[0]}, {v2.back()})) {
if (are_connected({v1.back()}, {v2[0]})) {
v1.insert(v1.end(), v2.begin(), v2.end());
}
else {
v1.insert(v1.end(), v2.rbegin(), v2.rend());
}
return v1;
}
int l=0, r=v1.size();
int mid(0);
while (l<r) {
mid=(l+r)/2;
if (are_connected(vector<int>(v1.begin(), v1.begin()+ mid + 1), v2)){
r=mid;
}
else l=mid+1;
}
int empl1=l;
l=0; r=v2.size();
while (l<r) {
mid=(l+r)/2;
if (are_connected(vector<int>(v2.begin(), v2.begin()+ mid + 1), {v1[empl1]})) r=mid;
else l=mid+1;
}
int empl2=l;
vector<int> ans = vector<int> (v1.begin() + empl1 + 1, v1.end());
ans.insert(ans.end(), v1.begin(), v1 . begin() + empl1 + 1);
ans.insert(ans.end(), v2.begin() + empl2, v2.end());
ans.insert(ans.end(),v2.begin(), v2.begin() + empl2);
return ans;
}
