#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> solve3(int n) {
vector<int> ans(n);
iota(ans.begin(), ans.end(), 0);
return ans;
}
vector<int> solve2(int n) {
vector<int> nxt(n);
int pair;
for (int i = 1; i < n; i++)
if (are_connected({0}, {i})) pair = i;
int head = 0, tail = pair;
nxt[head] = pair;
for (int i = 0; i < n; i++) {
if (i == 0 || i == pair) continue;
if (are_connected({head}, {i})) {
nxt[i] = head;
head = i;
} else {
nxt[tail] = i;
tail = i;
}
}
vector<int> ans;
while (true) {
ans.push_back(head);
if (head == tail) break;
head = nxt[head];
}
return ans;
}
int get_connected(vector<int> x, vector<int> y) {
if (x.empty() || y.empty()) return 0;
return are_connected(x, y);
}
vector<int> solve1(int n) {
vector<int> a({0}), b;
for (int i = 1; i < n; i++) {
int connect_a = get_connected(a, {i});
int connect_b = get_connected(b, {i});
if (!connect_a && !connect_b) {
a.insert(a.end(), b.begin(), b.end());
b = {i};
} else {
if (connect_b) {
swap(a, b);
swap(connect_a, connect_b);
}
// head
if (are_connected({a[0]}, {i})) a.insert(a.begin(), i);
// tail
else if (are_connected({a[a.size() - 1]}, {i}))
a.push_back(i);
else {
for (int j = 0; j < (int)a.size(); j++) {
if (are_connected({a[j]}, {i})) {
// [i] + [j, ...] + [0, ..., j-1]
vector<int> vec;
vec.push_back(i);
for (int k = j; k < (int)a.size(); k++) vec.push_back(a[k]);
for (int k = 0; k < j; k++) vec.push_back(a[k]);
a = vec;
break;
}
}
}
if (connect_b) {
// connect to head
if (are_connected({b[0]}, {i})) {
// [bn, ..., b0] + [a0, ..., an]
reverse(b.begin(), b.end());
b.insert(b.end(), a.begin(), a.end());
a = b;
b = {};
}
// connect to tail
else if (are_connected({b[b.size() - 1]}, {i})) {
// [b0, ..., bn] + [a0, ..., an]
b.insert(b.end(), a.begin(), a.end());
a = b;
b = {};
}
// connect to middle
else {
for (int j = 0; j < (int)b.size(); j++) {
if (are_connected({b[j]}, {i})) {
// // [bj+1, ..., bn] [b0, ..., bj] [a0, ..., an]
vector<int> vec;
for (int k = j + 1; k < (int)b.size(); k++) vec.push_back(b[k]);
for (int k = 0; k <= j; k++) vec.push_back(b[k]);
vec.insert(vec.end(), a.begin(), a.end());
a = vec;
b = {};
break;
}
}
}
}
}
}
if (a.size() > b.size()) return a;
return b;
}
std::vector<int> longest_trip(int n, int density) {
if (density == 3) return solve3(n);
if (density == 2) return solve2(n);
if (density == 1) return solve1(n);
return {};
}
