#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#define cerr if (false) cout
#endif
struct info {
vector<int> A;
vector<int> B;
vector<int> ord;
};
int N;
bool g[256][256];
bool are_con(vector<int> a, vector<int> b) {
for (int x : a) {
for (int y : b) {
if (g[x][y])
return true;
}
}
return false;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
vector<int> operator + (vector<int> a, vector<int> b) {
for (int c : b) a.push_back(c);
return a;
}
void print(vector<int> a) {
cerr << '{';
for (int c : a)
cerr << c << ' ';
cerr << '}';
cerr << '\n';
}
vector<int> fin(vector<int> V, int x) {
for (int i = 0; i < (int)V.size() - 1; i++) {
if (V[i] == x) swap(V[i], V[i + 1]);
}
assert(V.back() == x);
return V;
}
vector<int> beg(vector<int> V, int x) {
for (int i = (int)V.size() - 1; i > 0; i--) {
if (V[i] == x) swap(V[i], V[i - 1]);
}
assert(V[0] == x);
return V;
}
vector<int> connect(vector<int> A, vector<int> B) {
int st = -1;
for (int c : B) {
if (are_con({A.back()}, {c})) {
st = c;
break;
}
}
assert(st != -1);
return A + beg(B, st);
};
info recursion(vector<int> V) {
if ((int)V.size() == 1)
return {V, {}, V};
vector<int> A, B;
vector<bool> us(N);
int p = V[rnd() % (int)V.size()];
cerr << "chosen vertex: " << p << '\n';
for (int c : V) if (p != c) {
if (!are_con({p}, {c})) {
B.push_back(c);
us[c] = true;
}
}
if (B.empty()) {
info res;
cerr << p << " is a star\n";
V.erase(find(V.begin(), V.end(), p));
info m = recursion(V);
if (m.ord.empty()) {
res.ord = m.A + vector<int>{p} + m.B;
} else {
res.ord = m.ord;
res.ord.push_back(p);
}
return res;
}
for (int c : V) {
if (us[c]) continue;
if (!are_con({c}, B)) {
A.push_back(c);
us[c] = true;
}
}
cerr << "Division: \n";
print(A);
print(B);
cerr << '\n';
shuffle(A.begin(), A.end(), rnd);
shuffle(B.begin(), B.end(), rnd);
vector<int> v1;
for (int c : V)
if (!us[c])
v1.push_back(c);
if (v1.empty())
return {A, B, {}};
info M = recursion(v1);
info res;
if (!M.ord.empty()) {
res.ord = fin(A, p) + connect(M.ord, B);
return res;
}
for (int it = 0; it < 2; it++) {
if ((int)A.size() == 1) {
res.ord = M.A + A + connect(M.B, B);
return res;
}
swap(A, B);
}
int c = A[(A[0] == p)], t = M.A[0];
if (are_con({c}, {t})) {
res.ord = fin(M.A, t) + beg(fin(A, p), c) + connect(M.B, B);
} else {
res.ord = fin(A, p) + connect(M.B, B) + beg(M.A, t);
}
return res;
}
vector<int> longest_trip(int N_ins, int D) {
N = N_ins;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
g[i][j] = 0;
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++) {
g[i][j] = g[j][i] = are_connected({i}, {j});
}
vector<int> v(N);
for (int i = 0; i < N; i++) v[i] = i;
info res = recursion(v);
if (res.ord.empty()) {
if ((int)res.A.size() < (int)res.B.size())
swap(res.A, res.B);
return res.A;
}
return res.ord;
}
