#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 256;
int n;
mt19937 rnd(200);
pair<int, int> getEdge(vector<int> a, vector<int> b) {
if (a.size() == 1 && b.size() == 1)
return {a[0], b[0]};
vector<int> c, d;
if (a.size() == 1) {
for (int i = 0; i < (int)b.size() / 2; i++)
c.push_back(b[i]);
for (int i = (int)b.size() / 2; i < (int)b.size(); i++)
d.push_back(b[i]);
if (are_connected(a, d))
return getEdge(a, d);
return getEdge(a, c);
}
for (int i = 0; i < (int)a.size() / 2; i++)
c.push_back(a[i]);
for (int i = (int)a.size() / 2; i < (int)a.size(); i++)
d.push_back(a[i]);
if (are_connected(c, b))
return getEdge(c, b);
return getEdge(d, b);
}
void shiftRight(vector<int> &v) {
int aux = v.back();
for (int i = v.size() - 1; i >= 1; i--)
v[i] = v[i - 1];
v[0] = aux;
}
void check(vector<int> v) {
for (int i = 0; i < (int)v.size() - 1; i++)
assert(are_connected({v[i]}, {v[i + 1]}));
}
vector<int> longest_trip(int N, int D) {
n = N;
vector<int> perm(n, 0);
for (int i = 0; i < n; i++)
perm[i] = i;
shuffle(perm.begin(), perm.end(), rnd);
vector<int> path(1, perm[0]);
vector<int> clique;
for (int i = 1; i < n; i++) {
int v = perm[i];
if (!are_connected({path.back()}, {v})) {
clique.push_back(v);
continue;
}
path.push_back(v);
if (clique.empty())
continue;
if (are_connected({v}, clique)) {
pair<int, int> e = getEdge({v}, clique);
path.push_back(e.second);
for (int v: clique) {
if (v == e.second)
continue;
// assert(are_connected({path.back()}, {v}));
path.push_back(v);
}
clique.clear();
}
}
if (clique.empty()) {
// assert((int)path.size() == n);
// check(path);
return path;
}
if (!are_connected(path, clique)) {
// assert((int)path.size() + (int)clique.size() == n);
// check(path);
// check(clique);
if (path.size() > clique.size())
return path;
return clique;
}
pair<int, int> e;
if (!are_connected({path.back()}, clique)) {
e = getEdge(path, clique);
// assert(are_connected({e.first}, {e.second}));
if (e.first == path[0])
reverse(path.begin(), path.end());
else {
while (path.back() != e.first)
shiftRight(path);
}
} else
e = getEdge({path.back()}, clique);
path.push_back(e.second);
for (int v: clique) {
if (v == e.second)
continue;
// assert(are_connected({path.back()}, {v}));
path.push_back(v);
}
// assert((int)path.size() == n);
// check(path);
return path;
}
