#include <vector>
#include <random>
#include <algorithm>
using namespace std;
// 交互库提供的函数
bool are_connected(std::vector<int> A, std::vector<int> B);
std::vector<int> longest_trip(int N, int D) {
if (N == 1) return {0};
if (N == 2) {
if (are_connected({0}, {1})) return {0, 1};
return {0}; // 若两个都不连通，最长即为 1 个
}
vector<int> A = {0};
vector<int> B;
bool known_non_edge = false; // 记录 A 的末尾和 B 的末尾是否确认没有边
mt19937 rng(1337);
// 第一阶段: 将所有的点划分至 A 和 B
for (int i = 1; i < N; ++i) {
if (B.empty()) {
if (are_connected({A.back()}, {i})) {
A.push_back(i);
known_non_edge = false;
} else {
B.push_back(i);
known_non_edge = true;
}
} else {
bool swap_AB = rng() % 2; // 随机决定优先查询顺序
if (swap_AB) swap(A, B);
if (are_connected({A.back()}, {i})) {
A.push_back(i);
known_non_edge = false;
} else {
if (known_non_edge) {
B.push_back(i);
known_non_edge = true; // 必然 i 不连 A.back(), 维持性质
} else {
if (are_connected({B.back()}, {i})) {
B.push_back(i);
known_non_edge = true;
} else {
// 两边都不连通，依据 D >= 1，A.back() 和 B.back() 之间必定存在一条道路
vector<int> next_A = A;
for (int j = (int)B.size() - 1; j >= 0; --j) {
next_A.push_back(B[j]);
}
A = next_A;
B = {i};
known_non_edge = false;
}
}
}
}
}
if (B.empty()) return A;
// 第二阶段: 合并路径
if (!are_connected(A, B)) {
return A.size() > B.size() ? A : B;
}
if (are_connected({A.back()}, {B.front()})) {
vector<int> res = A;
res.insert(res.end(), B.begin(), B.end());
return res;
}
if (are_connected({A.back()}, {B.back()})) {
vector<int> res = A;
for (int i = (int)B.size() - 1; i >= 0; --i) res.push_back(B[i]);
return res;
}
if (are_connected({A.front()}, {B.front()})) {
vector<int> res;
for (int i = (int)A.size() - 1; i >= 0; --i) res.push_back(A[i]);
res.insert(res.end(), B.begin(), B.end());
return res;
}
if (are_connected({A.front()}, {B.back()})) {
vector<int> res;
for (int i = (int)A.size() - 1; i >= 0; --i) res.push_back(A[i]);
for (int i = (int)B.size() - 1; i >= 0; --i) res.push_back(B[i]);
return res;
}
// 倘若四个边缘都无法连接，它们内部必含一圈内环。采用二分查找寻找 A 和 B 的直接连接线。
int low = 0, high = A.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
vector<int> pref_A(A.begin(), A.begin() + mid + 1);
if (are_connected(pref_A, B)) {
high = mid;
} else {
low = mid + 1;
}
}
int i = low;
low = 0; high = B.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
vector<int> pref_B(B.begin(), B.begin() + mid + 1);
if (are_connected({A[i]}, pref_B)) {
high = mid;
} else {
low = mid + 1;
}
}
int j = low;
vector<int> res;
for (int k = i + 1; k < (int)A.size(); ++k) res.push_back(A[k]);
for (int k = 0; k <= i; ++k) res.push_back(A[k]);
for (int k = j; k < (int)B.size(); ++k) res.push_back(B[k]);
for (int k = 0; k < j; ++k) res.push_back(B[k]);
return res;
}
