#include "longesttrip.h"
#include <queue>
#include <stdio.h>
#include <cassert>
using namespace std;
const int MAX_N = 256;
int n;
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, c))
return getEdge(a, c);
return getEdge(a, d);
}
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> path(1, 0);
vector<int> clique;
for (int i = 1; i < n; i++) {
if (!are_connected({path.back()}, {i})) {
clique.push_back(i);
continue;
}
path.push_back(i);
if (clique.empty())
continue;
if (are_connected({i}, clique)) {
pair<int, int> e = getEdge({i}, clique);
path.push_back(e.second);
for (int v: clique) {
if (v != e.second) {
path.push_back(v);
assert(are_connected({path.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 = getEdge(path, clique);
assert(are_connected({e.first}, {e.second}));
while (path.back() != e.first)
shiftRight(path);
for (int v: clique) {
assert(are_connected({path.back()}, {v}));
path.push_back(v);
}
assert((int)path.size() == n);
check(path);
return path;
}
