#include "longesttrip.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define ss(a) set<a>
#define pp(a, b) pair<a, b>
#define mm(a, b) map<a, b>
#define qq(a) queue<a>
#define pq(a) priority_queue<a>
#define ump(a, b) unordered_map<a, b>
#define ANDROID \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define elif else if
#define endl "\n"
#define pb push_back
#define ins insert
#define logi __lg
#define sqrt sqrtl
#define mpr make_pair
using namespace std;
using namespace __cxx11;
using namespace __gnu_pbds;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 256;
vv(ll) g[N];
bool mat[N][N];
std::vector<int> longest_trip(int n, int d)
{
for (ll i = 0; i < n; i++)
for (ll j = 0; j < n; j++)
mat[i][j] = 0;
for (ll i = 0; i < n; i++)
g[i].clear();
vv(int) ans;
if (d == 3)
{
for (ll i = 0; i < n; i++)
ans.pb(i);
return ans;
}
if (d == 2)
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (are_connected({i}, {j}))
g[i].pb(j), g[j].pb(i), mat[i][j] = mat[j][i] = true;
vector<int> ans;
ll found = 0;
for (ll i = 0; i + 1 < n; i++)
if (mat[i][i + 1])
{
ans.push_back(i), ans.push_back(i + 1), found = i;
break;
}
for (ll i = 0; i < n; i++)
if (i != found and i != found + 1)
{
if (mat[ans.front()][i])
ans.insert(ans.begin(), i);
else
ans.push_back(i);
}
return ans;
}
vector<int> comp, comp1;
ll p[n];
iota(p, p + n, 0);
shuffle(p, p + n, rng);
for (int i : p)
if (comp1.empty())
{
if (!are_connected({comp.back()}, {i}))
comp1 = {i};
else
comp.push_back(i);
}
else
{
bool ok = are_connected({comp.back()}, {i});
if (ok)
{
bool ok1 = are_connected({comp1.back()}, {i});
if (ok1)
{
comp.push_back(i);
for (ll j : comp1)
comp.push_back(j);
comp1.clear();
}
else
comp.push_back(i);
}
else
comp1.push_back(i);
}
if (comp1.empty())
return comp;
if (comp.size() > comp1.size())
swap(comp, comp1);
if (!are_connected(comp, comp1))
return comp1;
if (comp.size() >= 3)
{
bool ok = are_connected({comp.front()}, {comp.back()});
if (!ok)
{
ans = comp;
if (!are_connected({comp.back()}, {comp1.front()}))
reverse(ans.begin(), ans.end());
for (ll i : comp1)
ans.push_back(i);
return ans;
}
swap(comp, comp1);
ok = are_connected({comp.front()}, {comp.back()});
if (!ok)
{
ans = comp;
if (!are_connected({comp.back()}, {comp1.front()}))
reverse(ans.begin(), ans.end());
for (ll i : comp1)
ans.push_back(i);
return ans;
}
swap(comp, comp1);
}
ll l = 0, r = comp.size() - 1;
int first = comp.size() - 1;
vector<int> tmp;
while (l <= r)
{
tmp.clear();
ll mid = (l + r) >> 1;
for (ll i = 0; i <= mid; i++) tmp.push_back(comp[i]);
if (are_connected(tmp, comp1))
r = mid - 1, first = mid;
else
l = mid + 1;
}
l = 0, r = comp1.size() - 1;
int second = comp1.size() - 1;
while (l <= r)
{
tmp.clear();
ll mid = (l + r) >> 1;
for (ll i = 0; i <= mid; i++) tmp.push_back(comp1[i]);
if (are_connected({comp[first]}, tmp))
r = mid - 1, second = mid;
else
l = mid + 1;
}
for (ll i = first + comp.size() - 1; i >= first; i--)
ans.push_back(comp[i % comp.size()]);
for (ll i = second; i < second + comp1.size(); i++)
ans.push_back(comp1[i % comp1.size()]);
return ans;
}
