#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand_(const int l = 0, const int r = INT_MAX) {
return uniform_int_distribution<int>(l, r)(rng);
}
bool query(const vt<int> A, const vt<int> B) {
return are_connected(A, B);
}
vt<int> longest_trip(int N, int D) {
vt<int> line_a = {0}, line_b;
FOR(i, 1, N-1) {
if (rand_() & 1 && size(line_b))
swap(line_a, line_b);
if (query({line_a.back()}, {i})) {
line_a.push_back(i);
} else if (!size(line_b) || query({line_b.back()}, {i})) {
line_b.push_back(i);
} else {
reverse(all(line_b));
line_a.insert(line_a.end(), all(line_b));
line_b = {i};
}
}
if (!size(line_b))
return line_a;
FOR(i, 0, 3) {
if (query({line_a[0]}, {line_b[0]})) {
reverse(all(line_a));
line_a.insert(line_a.end(), all(line_b));
return line_a;
}
reverse(all(line_b));
if (i & 1)
reverse(all(line_a));
}
const auto check = [&](const vt<int> A, const vt<int> B) {
int lo = 0, hi = size(A);
while (lo < hi) {
const int mid = lo + hi >> 1;
if (query(vt<int>(A.begin(), A.begin() + mid + 1), B))
hi = mid;
else
lo = mid + 1;
}
return lo;
};
const int a = check(line_a, line_b);
if (a == size(line_a))
return size(line_a) > size(line_b) ? line_a : line_b;
const int b = check(line_b, {line_a[a]});
rotate(line_a.begin(), line_a.begin() + a + 1, line_a.end());
rotate(line_b.begin(), line_b.begin() + b, line_b.end());
line_a.insert(line_a.end(), all(line_b));
return line_a;
}
