#include "longesttrip.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
typedef long long llong;
const int MAXN = 256 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;
int n;
std::mt19937 rng(420);
std::vector <int> perm;
std::vector <int> convert(const std::vector <int> &v)
{
std::vector <int> res;
for (const int &i : v) res.push_back(perm[i]);
return res;
}
bool areConnected(std::vector <int> a, std::vector <int> b)
{
std::vector <int> A, B;
for (const int &i : a) A.push_back(perm[i]);
for (const int &i : b) B.push_back(perm[i]);
return are_connected(A, B);
}
bool areConnected(int a, int b)
{
std::vector <int> A, B;
A.push_back(a);
B.push_back(b);
return areConnected(A, B);
}
std::vector <int> longest_trip(int N, int D)
{
n = N;
std::vector <int> a, b;
perm.resize(n);
std::iota(perm.begin(), perm.end(), 0);
std::shuffle(perm.begin(), perm.end(), rng);
a.push_back(0);
b.push_back(1);
for (int i = 2 ; i < n ; i += 2)
{
assert(a.size() && b.size());
if (i == n - 1)
{
if (areConnected(a.back(), i))
{
a.push_back(i);
} else if (areConnected(b.back(), i))
{
b.push_back(i);
} else
{
std::reverse(b.begin(), b.end());
for (const int &u : b)
{
a.push_back(u);
}
b.clear();
b.push_back(i);
}
break;
}
if (areConnected(i, i + 1))
{
if (areConnected(a.back(), i))
{
a.push_back(i);
a.push_back(i + 1);
continue;
}
if (areConnected(b.back(), i))
{
b.push_back(i);
b.push_back(i + 1);
continue;
}
std::reverse(b.begin(), b.end());
for (const int &u : b)
{
a.push_back(u);
}
b.clear();
b.push_back(i);
b.push_back(i + 1);
continue;
}
int edgeA = i;
int edgeB = i;
if (!areConnected(a.back(), i))
{
edgeA = i + 1;
}
if (!areConnected(b.back(), i))
{
edgeB = i + 1;
}
if (edgeA != edgeB)
{
a.push_back(edgeA);
b.push_back(edgeB);
continue;
}
a.push_back(edgeA);
std::reverse(b.begin(), b.end());
for (const int &u : b)
{
a.push_back(u);
}
b.clear();
b.push_back(edgeB ^ 1);
}
if (a.size() < b.size())
{
std::swap(a, b);
}
if (b.empty())
{
return convert(a);
}
if (!areConnected(a, b))
{
return convert(a);
}
if (areConnected({a[0]}, {b[0]}))
{
std::reverse(a.begin(), a.end());
for (int i = 0 ; i < b.size() ; ++i)
{
a.push_back(b[i]);
}
return convert(a);
}
if (b.size() > 1 && areConnected({a[0]}, {b.back()}))
{
std::reverse(b.begin(), b.end());
std::reverse(a.begin(), a.end());
for (int i = 0 ; i < b.size() ; ++i)
{
a.push_back(b[i]);
}
return convert(a);
}
if (areConnected({b[0]}, {a.back()}))
{
for (int i = 0 ; i < b.size() ; ++i)
{
a.push_back(b[i]);
}
return convert(a);
}
int aPos, bPos;
int l = -1, r = a.size() - 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
std::vector <int> prefix(a.begin(), a.begin() + mid + 1);
if (!areConnected(prefix, b)) l = mid;
else r = mid;
}
aPos = r;
std::vector <int> prefixA(a.begin(), a.begin() + aPos + 1);
l = -1; r = b.size() - 1;
while (l < r - 1)
{
mid = (l + r) / 2;
std::vector <int> prefixB(b.begin(), b.begin() + mid + 1);
if (!areConnected(prefixA, prefixB)) l = mid;
else r = mid;
}
bPos = r;
for (int i = 0 ; i < aPos ; ++i)
{
a.push_back(a[0]);
a.erase(a.begin());
}
for (int i = 0 ; i < bPos ; ++i)
{
b.push_back(b[0]);
b.erase(b.begin());
}
std::reverse(a.begin(), a.end());
for (int i = 0 ; i < b.size() ; ++i)
{
a.push_back(b[i]);
}
return convert(a);
}
