#include "longesttrip.h"
#include <chrono>
#include <random>
#include <algorithm>
#include <map>
using namespace std;
std::vector<int> longest_trip(int N, int D)
{
map<pair<int, int>, bool> memo;
auto are_pair_connected = [&](int u, int v)
{
if (u > v)
swap(u, v);
if (auto iter = memo.find(make_pair(u, v)); iter == memo.end())
memo[make_pair(u, v)] = are_connected({u}, {v});
return memo[make_pair(u, v)];
};
vector<vector<int>> trips;
for (int i = 0; i < N; i++)
trips.emplace_back(vector{i});
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
shuffle(trips.begin(), trips.end(), rd);
while (trips.size() >= 3)
{
vector<vector<int>> last(trips.end() - 3, trips.end());
trips.resize(trips.size() - (size_t)3);
if (are_pair_connected(last[1].front(), last[2].front()))
swap(last[0], last[2]);
else if (are_pair_connected(last[0].front(), last[2].front()))
swap(last[1], last[2]);
reverse(last[0].begin(), last[0].end());
last[0].insert(last[0].end(), last[1].begin(), last[1].end());
trips.emplace_back(last[2]);
trips.emplace_back(last[0]);
}
// Case 1: not connected two components
if (!are_connected(trips[0], trips[1]))
return trips[0].size() >= trips[1].size() ? trips[0] : trips[1];
// Case 2: end points directly connecting
for (auto t = 0; t < 2; t++)
{
if (trips[1].size() >= 3 && are_connected({trips[0].back()}, {trips[1].front(), trips[1].back()}))
{
if (are_connected({trips[0].back()}, {trips[1].front()}))
trips[0].insert(trips[0].end(), trips[1].begin(), trips[1].end());
else
trips[0].insert(trips[0].end(), trips[1].rbegin(), trips[1].rend());
return trips[0];
}
swap(trips[0], trips[1]);
}
// Case 3: two cycles
auto reduce = [](vector<int> target, vector<int> against) -> int
{
while (target.size() > 1)
{
size_t mid = target.size() / 2;
if (are_connected(vector(target.begin(), target.begin() + mid), against))
target.resize(mid);
else
target = vector(target.begin() + mid, target.end());
}
return target.front();
};
int u = reduce(trips[0], trips[1]);
int v = reduce(trips[1], {u});
rotate(trips[0].begin(), find(trips[0].begin(), trips[0].end(), u), trips[0].end());
rotate(trips[1].begin(), find(trips[1].begin(), trips[1].end(), v), trips[1].end());
reverse(trips[0].begin(), trips[0].end());
trips[0].insert(trips[0].end(), trips[1].begin(), trips[1].end());
return trips[0];
}
