#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);
}
void join(vector<deque<int>> &comp, int u, int v) {
int a = -1;
int b = -1;
for (int i = 0; i < comp.size(); i++) {
if (!comp[i].empty()) {
if (comp[i].front() == u) {
reverse(comp[i].begin(), comp[i].end());
a = i;
} else if (comp[i].back() == u) {
a = i;
}
if (comp[i].front() == v) {
b = i;
} else if (comp[i].back() == v) {
reverse(comp[i].begin(), comp[i].end());
b = i;
}
}
}
comp[a].insert(comp[a].end(), comp[b].begin(), comp[b].end());
comp.erase(comp.begin() + b);
}
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);
set<pair<int, int>> known;
while (comp.size() > 2) {
int i = 0;
int j = 1;
int k = 2;
int u = comp[i].back();
int v = comp[j].back();
int w = comp[k].back();
int vv = comp[j].front();
int ww = comp[k].front();
if (known.count(minmax(u, v)) + known.count(minmax(v, w)) +
known.count(minmax(u, w)) ==
2) {
if (!known.count(minmax(u, v)))
join(comp, u, v);
else if (!known.count(minmax(u, w)))
join(comp, u, w);
else
join(comp, v, w);
continue;
}
swap(v, vv);
if (known.count(minmax(u, v)) + known.count(minmax(v, w)) +
known.count(minmax(u, w)) ==
2) {
if (!known.count(minmax(u, v)))
join(comp, u, v);
else if (!known.count(minmax(u, w)))
join(comp, u, w);
else
join(comp, v, w);
continue;
}
swap(w, ww);
if (known.count(minmax(u, v)) + known.count(minmax(v, w)) +
known.count(minmax(u, w)) ==
2) {
if (!known.count(minmax(u, v)))
join(comp, u, v);
else if (!known.count(minmax(u, w)))
join(comp, u, w);
else
join(comp, v, w);
continue;
}
swap(v, vv);
if (known.count(minmax(u, v)) + known.count(minmax(v, w)) +
known.count(minmax(u, w)) ==
2) {
if (!known.count(minmax(u, v)))
join(comp, u, v);
else if (!known.count(minmax(u, w)))
join(comp, u, w);
else
join(comp, v, w);
continue;
}
swap(w, ww);
if (!known.count(minmax(u, v)) && are_connected({u}, {v})) {
join(comp, u, v);
} else if (!known.count(minmax(vv, ww)) && are_connected({vv}, {ww})) {
known.insert(minmax(u, v));
join(comp, ww, vv);
} else {
known.insert(minmax(u, v));
known.insert(minmax(vv, ww));
if (known.count(minmax(u, v)) + known.count(minmax(v, w)) +
known.count(minmax(u, w)) ==
2) {
if (!known.count(minmax(u, v)))
join(comp, u, v);
else if (!known.count(minmax(u, w)))
join(comp, u, w);
else
join(comp, v, w);
continue;
}
if (!known.count(minmax(u, w)) && are_connected({u}, {w})) {
reverse(comp[j].begin(), comp[j].end());
join(comp, u, w);
} else {
known.insert(minmax(u, w));
join(comp, v, w);
}
}
}
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());
}
