#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
bool are_connected(vector<int> A, vector<int> B);
vector<int> connect(vector<int> a, vector<int> b) {
reverse(b.begin(), b.end());
for (auto x: b) a.push_back(x);
return a;
}
vector<int> connect_cycles(vector<int> a, int _i, vector<int> b, int _j) {
vector<int> res;
for (int i = (_i + 1) % a.size(); i != _i; i = (i + 1) % a.size()) {
res.push_back(a[i]);
}
res.push_back(a[_i]);
for (int i = _j; (i + 1) % b.size() != _j; i = (i + 1) % b.size()) {
res.push_back(b[i]);
}
res.push_back(b[(_j - 1 + b.size()) % b.size()]);
return res;
}
vector<int> longest_trip(int n, int d) {
vector<int> pathA = {0}, pathB = {1};
for (int i = 2; i < n; i++) {
if (are_connected({pathA.back()}, {i})) {
pathA.push_back(i);
} else if (are_connected({pathB.back()}, {i})) {
pathB.push_back(i);
} else {
pathA = connect(pathA, pathB);
pathB = {i};
}
}
if (pathA.size() < pathB.size()) swap(pathA, pathB);
if (are_connected(pathA, pathB) == false) return pathA;
if (are_connected({pathB.back()}, {pathA.back()})) {
return connect(pathA, pathB);
}
reverse(pathA.begin(), pathA.end());
if (are_connected({pathB.back()}, {pathA.back()})) {
return connect(pathA, pathB);
}
// A è ciclico
reverse(pathB.begin(), pathB.end());
if (are_connected({pathB.back()}, {pathA.back()})) {
return connect(pathA, pathB);
}
// B è ciclico
int i = 0, j = 0;
for (int k = 1 << 9; k; k >>= 1) {
if (i + k >= pathA.size()) continue;
vector<int> check;
for (int x = 0; x < i + k; x++) check.push_back(pathA[x]);
if (are_connected(pathB, check) == false) i += k;
}
for (int k = 1 << 9; k; k >>= 1) {
if (j + k >= pathB.size()) continue;
vector<int> check;
for (int x = 0; x < j + k; x++) check.push_back(pathB[x]);
if (are_connected({pathA[i]}, check) == false) j += k;
}
return connect_cycles(pathA, i, pathB, j);
}
