#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
std::vector<int> longest_trip(int N, int D)
{
int n = N;
vector<int> v1;
vector<int> v2;
v1.push_back(0);
v2.push_back(1);
for (int x = 2; x < n; ++x)
{
if (are_connected(vector<int>{x}, vector<int>{v1.back()}))
v1.push_back(x);
else if (are_connected(vector<int>{x}, vector<int>{v2.back()}))
v2.push_back(x);
else
{
reverse(all(v2));
for (int i = 0; i < sz(v2); ++i)
v1.push_back(v2[i]);
v2.clear();
v2.push_back(x);
}
}
if (are_connected(vector<int>{v1.back()}, vector<int>{v2.back()}))
{
reverse(all(v2));
for (int i = 0; i < sz(v2); ++i)
v1.push_back(v2[i]);
v2.clear();
return v1;
}
reverse(all(v1));
if (are_connected(vector<int>{v1.back()}, vector<int>{v2.back()}))
{
reverse(all(v2));
for (int i = 0; i < sz(v2); ++i)
v1.push_back(v2[i]);
v2.clear();
return v1;
}
reverse(all(v2));
if (are_connected(vector<int>{v1.back()}, vector<int>{v2.back()}))
{
reverse(all(v2));
for (int i = 0; i < sz(v2); ++i)
v1.push_back(v2[i]);
v2.clear();
return v1;
}
reverse(all(v1));
if (are_connected(vector<int>{v1.back()}, vector<int>{v2.back()}))
{
reverse(all(v2));
for (int i = 0; i < sz(v2); ++i)
v1.push_back(v2[i]);
v2.clear();
return v1;
}
if (!are_connected(v1, v2))
{
if (sz(v2) > sz(v1))
swap(v1, v2);
return v1;
}
int x = -1;
int l = 0, r = sz(v1) - 1;
while (l <= r)
{
int m = (l + r) / 2;
vector<int> u;
for (int i = 0; i <= m; ++i)
u.push_back(v1[i]);
if (are_connected(u, v2))
{
x = m;
r = m - 1;
}
else
l = m + 1;
}
assert(x != -1);
int y = -1;
l = 0, r = sz(v2) - 1;
while (l <= r)
{
int m = (l + r) / 2;
vector<int> u;
for (int i = 0; i <= m; ++i)
u.push_back(v2[i]);
if (are_connected(u, vector<int>{v1[x]}))
{
y = m;
r = m - 1;
}
else
l = m + 1;
}
assert(y != -1);
vector<int> u;
for (int i = 0; i < sz(v1); ++i)
{
u.push_back(v1[(x + 1 + i) % sz(v1)]);
}
for (int i = 0; i < sz(v2); ++i)
{
u.push_back(v2[(y + i) % sz(v2)]);
}
return u;
}
