#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N, int D) {
if (D == 3) {
vector<int> ans(N);
iota(ans.begin(), ans.end(), 0);
return ans;
}
if (D == 2) {
deque<int> ans;
vector<int> cl(N, 0);
if (are_connected({0}, {1})) {
cl[0] = cl[1] = 1;
ans.push_front(0); ans.push_back(1);
} else {
cl[0] = cl[2] = 1;
ans.push_front(0); ans.push_back(2);
}
while (ans.size() < N) {
for (int i = 0; i < N; i++)
if (!cl[i]) {
if (are_connected({ans.front()}, {i})) ans.push_front(i);
else ans.push_back(i);
cl[i] = 1;
break;
}
}
return vector<int>(ans.begin(), ans.end());
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> A(N, 0);
iota(A.begin(), A.end(), 0);
shuffle(A.begin(), A.end(), rng);
vector<int> pathA, pathB;
pathA.emplace_back(A[0]);
pathB.emplace_back(A[1]);
for (int i = 2; i < N; i++)
if (are_connected({pathA.back()}, {pathB.back()})) {
for (int x = pathB.size()-1; x >= 0; x--) pathA.emplace_back(pathB[x]);
pathB.assign(1, A[i]);
} else are_connected({pathA.back()}, {A[i]}) ? pathA.emplace_back(A[i]) : pathB.emplace_back(A[i]);
if (!are_connected(vector<int>(pathA.begin(), pathA.end()), vector<int>(pathB.begin(), pathB.end()))) return pathA.size() < pathB.size() ? pathB : pathA;
if (are_connected({pathA.back()}, {pathB.back()})) {
for (int i = pathB.size()-1; i >= 0; i--) pathA.emplace_back(pathB[i]);
return pathA;
}
int lo, hi;
lo = -1; hi = pathA.size() - 1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (are_connected(vector<int>(pathA.begin(), pathA.begin()+mid+1), pathB)) hi = mid;
else lo = mid;
}
int pA = hi;
lo = -1; hi = pathB.size() - 1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (are_connected({pathA[pA]}, vector<int>(pathB.begin(), pathB.begin()+mid+1))) hi = mid;
else lo = mid;
}
int pB = hi;
vector<int> ans;
for (int i = pA + 1; i < pathA.size(); i++) ans.emplace_back(pathA[i]);
for (int i = 0; i <= pA; i++) ans.emplace_back(pathA[i]);
for (int i = pB; i < pathB.size(); i++) ans.emplace_back(pathB[i]);
for (int i = 0; i < pB; i++) ans.emplace_back(pathB[i]);
return ans;
}
