#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int dc_left(vector<int> a, vector<int> b) {
if (a.size() == 1)
return a.back();
vector<int> left(a.begin(), a.begin() + a.size() / 2);
vector<int> right(a.begin() + a.size() / 2, a.end());
if (are_connected(left, b))
return dc_left(left, b);
else
return dc_left(right, b);
}
int dc_right(vector<int> a, vector<int> b) {
if (b.size() == 1)
return b.back();
vector<int> left(b.begin(), b.begin() + b.size() / 2);
vector<int> right(b.begin() + b.size() / 2, b.end());
if (are_connected(a, left))
return dc_right(a, left);
else
return dc_right(a, right);
}
default_random_engine engine;
vector<int> longest_trip(int N, int D) {
vector<deque<int>> comp(N);
for (int i = 0; i < N; i++)
comp[i].push_back(i);
while (comp.size() > 2) {
sort(comp.begin(), comp.end(),
[](auto x, auto y) { return x.size() < y.size(); });
uniform_int_distribution<int> uid(0, 1);
if (uid(engine))
reverse(comp[0].begin(), comp[0].end());
if (uid(engine))
reverse(comp[1].begin(), comp[1].end());
if (uid(engine))
reverse(comp[2].begin(), comp[2].end());
vector<int> buf({0, 1, 2});
shuffle(buf.begin(), buf.end(), engine);
int i = buf[0];
int j = buf[1];
int k = buf[2];
int u = comp[i].back();
int v = comp[j].back();
int w = comp[k].back();
if (are_connected({v}, {w})) {
swap(u, w);
swap(i, k);
} else if (are_connected({u}, {w})) {
swap(v, w);
swap(j, k);
}
reverse(comp[j].begin(), comp[j].end());
comp[i].insert(comp[i].end(), comp[j].begin(), comp[j].end());
comp.erase(comp.begin() + j);
}
if (comp[0].size() < comp[1].size()) {
swap(comp[0], comp[1]);
}
if (are_connected({comp[0].back()}, {comp[1].back()})) {
reverse(comp[1].begin(), comp[1].end());
comp[0].insert(comp[0].end(), comp[1].begin(), comp[1].end());
} else if (are_connected({comp[0].back()}, {comp[1].front()})) {
comp[0].insert(comp[0].end(), comp[1].begin(), comp[1].end());
} else if (are_connected({comp[0].front()}, {comp[1].front()})) {
reverse(comp[0].begin(), comp[0].end());
comp[0].insert(comp[0].end(), comp[1].begin(), comp[1].end());
} else if (are_connected({comp[0].front()}, {comp[1].back()})) {
reverse(comp[0].begin(), comp[0].end());
reverse(comp[1].begin(), comp[1].end());
comp[0].insert(comp[0].end(), comp[1].begin(), comp[1].end());
} else if (are_connected(vector<int>(comp[0].begin(), comp[0].end()),
vector<int>(comp[1].begin(), comp[1].end()))) {
// two cycles, connected
int l = dc_left(vector<int>(comp[0].begin(), comp[0].end()),
vector<int>(comp[1].begin(), comp[1].end()));
int r = dc_right({l}, vector<int>(comp[1].begin(), comp[1].end()));
int l_idx = find(comp[0].begin(), comp[0].end(), l) - comp[0].begin();
int r_idx = find(comp[1].begin(), comp[1].end(), r) - comp[1].begin();
vector<int> ret;
for (int i = 0; i < comp[0].size(); i++)
ret.push_back(comp[0][(l_idx + 1 + i) % comp[0].size()]);
for (int i = 0; i < comp[1].size(); i++)
ret.push_back(comp[1][(r_idx + i) % comp[1].size()]);
return ret;
}
return vector<int>(comp[0].begin(), comp[0].end());
}
