#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> longest_trip(int N, int D)
{
list <int> l1,l2;
l1.push_back(0);
bool flag=true;
for (int i(1); i < N; i++) {
if (l2.empty()) l2.push_back(i), flag=true;
else if (are_connected({i},{l1.back()})) {
l1.push_back(i);
flag=true;
}
else if (flag && are_connected({i},{l2.front()})){
l2.push_front(i);
flag=false;
}
else {
l1.insert(l1.end(), l2.begin(), l2.end());
l2.clear();
l2.push_back(i);
flag=true;
}
}
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.size()==0) return v1;
if (!are_connected(v1, v2)) {
if (v1.size() > v2.size()) return v1;
return v2;
}
if (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 (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();
while (l<r) {
int 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) {
int 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;
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;
}
