#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
vector<int> b;
void pf(vector<int> &v, int x) {
v.push_back(0);
for (int i = v.size() - 1; i > 0; i--) v[i] = v[i - 1];
v[0] = x;
}
void pb(vector<int> &v, int x) {
v.push_back(x);
}
bool query(int x, int l, int r, vector<int> &v) {
vector<int> u;
for (int i = l; i < r; i++) u.push_back(v[i]);
return are_connected({x}, u);
}
int bin(int x, vector<int> &v) {
int l = 0, r = v.size(), m;
if (!query(x, l, r, v)) return -1;
while (r - l > 1) {
m = (l + r) / 2;
(query(x, l, m, v) ? r = m : l = m);
}
return l;
}
bool try_add(int x, vector<int> &v) {
if (!v.size()) {
pb(v, x);
return true;
}
if (v.size() == 1) {
if (are_connected({v[0]}, {x})) {
pb(v, x);
return true;
}
return false;
}
int y = v[0], z = v.back();
if (are_connected({y}, {x})) {
reverse(v.begin(), v.end());
pb(v, x);
return true;
}
if (are_connected({z}, {x})) {
pb(v, x);
return true;
}
int k = bin(x, v);
if (k == -1) return false;
vector<int> u;
for (int i = k + 1; i < v.size(); i++) pb(u, v[i]);
for (int i = 0; i <= k; i++) pb(u, v[i]);
v = u;
v.push_back(x);
return true;
}
void solve() {
for (int i = 2; i < N; i++) {
if (are_connected({a.back()}, {b.back()})) {
while (b.size()) {
a.push_back(b.back());
b.pop_back();
}
b.push_back(i);
continue;
}
if (are_connected({a.back()}, {i})) a.push_back(i);
else b.push_back(i);
}
}
vector<int> longest_trip(int N, int D) {
n = N;
a = {0};
b = {1};
solve();
if (a.size()<b.size()) swap(a,b);
if (!try_add(a.back(),b)) return a;
b.pop_back();
while (b.size()) {
a.push_back(b.back());
b.pop_back();
}
return a;
}
Compilation message
longesttrip.cpp: In function 'bool try_add(int, std::vector<int>&)':
longesttrip.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i = k + 1; i < v.size(); i++) pb(u, v[i]);
| ~~^~~~~~~~~~
longesttrip.cpp: In function 'void solve()':
longesttrip.cpp:68:25: error: 'N' was not declared in this scope
68 | for (int i = 2; i < N; i++) {
| ^
