#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int N;
const int MAXN = 256;
vector<int> adj[MAXN];
void connect(vector<int>& path1, vector<int>& path2) {
reverse(begin(path2), end(path2));
for (int j = 0; j < (int)path2.size(); ++j) {
path1.push_back(path2[j]);
}
path2.clear();
}
std::vector<int> longest_trip(int _N, int D)
{
N = _N;
vector<int> idx(N);
iota(begin(idx), end(idx), 0);
mt19937 rng(0);
shuffle(begin(idx), end(idx), rng);
vector<int> path1{idx[0]}, path2{idx[1]};
for (int j = 2; j < N; ++j) {
int i = idx[j];
if (are_connected({path1.back()}, {i})) {
path1.push_back(i);
} else if (are_connected({path2.back()}, {i})) {
path2.push_back(i);
} else {
assert(are_connected({path1.back()}, {path2.back()}));
connect(path1, path2);
path2.push_back(i);
}
}
if (path1.size() < path2.size()) swap(path1, path2);
if (path2.size() == 0) return path1;
if (!are_connected(path1, path2)) return path1;
if (are_connected({path1.back()}, {path2.back()})) {
connect(path1, path2);
return path1;
}
reverse(begin(path1), end(path1));
if (are_connected({path1.back()}, {path2.back()})) {
connect(path1, path2);
return path1;
}
reverse(begin(path1), end(path1));
reverse(begin(path2), end(path2));
if (are_connected({path1.back()}, {path2.back()})) {
connect(path1, path2);
return path1;
}
reverse(begin(path1), end(path1));
if (are_connected({path1.back()}, {path2.back()})) {
connect(path1, path2);
return path1;
}
reverse(begin(path1), end(path1));
reverse(begin(path2), end(path2));
cerr << "Path1 = ";
for (auto& u : path1) {
cerr << u << " ";
}
cerr << "\nPath2 = ";
for (auto& u : path2) {
cerr << u << " ";
}
cerr << "\n";
vector<int> super_path;
int l1 = 0, r1 = (int)path1.size();
int l2 = 0, r2 = (int)path2.size();
while (r1 - l1 > 1) {
int m1 = (l1 + r1) / 2;
if (are_connected(vector<int>(begin(path1) + l1, begin(path1) + m1),
vector<int>(begin(path2) + l2, begin(path2) + r2))) {
r1 = m1;
} else {
l1 = m1;
}
}
while (r2 - l2 > 1) {
int m2 = (l2 + r2) / 2;
if (are_connected(vector<int>(begin(path1) + l1, begin(path1) + r1),
vector<int>(begin(path2) + l2, begin(path2) + m2))) {
r2 = m2;
} else {
l2 = m2;
}
}
assert(l1 < (int)path1.size());
assert(l2 < (int)path2.size());
assert(are_connected(vector<int>(begin(path1) + l1, begin(path1) + r1),
vector<int>(begin(path2) + l2, begin(path2) + r2)));
// assert(r1 != (int)path1.size() && r2 != (int)path2.size());
// if (r1 == (int)path1.size()) r1 -= 1;
// if (r2 == (int)path2.size()) r2 -= 1;
if (r1 == (int)path1.size()) {
super_path.push_back(path1.back());
for (int i = 0; i < l1; ++i) {
super_path.push_back(path1[i]);
}
} else {
super_path.push_back(path1[r1]);
int ni = (r1 + 1) % (int)path1.size();
while (ni != r1) {
super_path.push_back(path1[ni]);
ni = (ni + 1) % (int)path1.size();
}
}
reverse(begin(super_path), end(super_path));
if (r2 == (int)path2.size()) {
super_path.push_back(path2.back());
for (int i = 0; i < l2; ++i) {
super_path.push_back(path2[i]);
}
} else {
super_path.push_back(path2[r2]);
int ni = (r2 + 1) % (int)path2.size();
while (ni != r2) {
super_path.push_back(path2[ni]);
ni = (ni + 1) % (int)path2.size();
}
}
return super_path;
}
