#include "longesttrip.h"
#include<bits/stdc++.h>
vector<int>longest_trip(int n, int d) {
vector<int> A, B;
A.push_back(0);
for(int i = 1; i < n; i++) {
vector<int> X, Y;
X.push_back(A.back());
Y.push_back(i);
if(are_connected(X, Y)) A.push_back(i);
else B.push_back(i);
X.clear(); Y.clear();
if(B.size()) {
X.push_back(A.back());
Y.push_back(B.back());
if(are_connected(X, Y))
while(B.size()) {
A.pb(B.back());
B.pop_back();
}
}
}
if(B.size() > A.size()) swap(A, B);
if(B.size() == 0) return A;
vector<int> X, Y;
X.push_back(A[0]);
Y.push_back(B[0]);
if(are_connected(X, Y)) {
reverse(A.begin(), A.end());
for(auto i : B) A.push_back(i);
return A;
}
Y.clear(); Y.push_back(B.back());
if(are_connected(X, Y)) {
for(auto i : A) B.push_back(i);
return B;
}
X.clear(); Y.clear();
X.push_back(A.back()); Y.push_back(B[0]);
if(are_connected(X, Y)) {
for(auto i : B) A.push_back(i);
return A;
}
if(!are_connected(A, B)) return A;
int l = 0, r = A.size() - 1;
while(l < r) {
int mid = (l + r) / 2;
vector<int> tmp;
for(int i = 0; i < mid + 1; i++) tmp.push_back(A[i]);
if(are_connected(tmp, B)) r = mid; else l = mid + 1;
}
X.clear(); X.push_back(A[l]);
int s = 0, e = B.size()-1;
while(s < e) {
int mid = (s + e) / 2;
vector<int> tmp;
for(int i = 0; i < mid + 1; i++) tmp.push_back(B[i]);
if(are_connected(X, tmp)) e = mid; else s = mid + 1;
}
vector<int> ans;
for(int i = 0; i < A.size(); i++) ans.push_back(A[(i + l + 1) % A.size()]);
for(int i = 0; i < B.size(); i++) ans.push_back(B[(i + s) % B.size()]);
return ans;
}
Compilation message
longesttrip.cpp:4:1: error: 'vector' does not name a type
4 | vector<int>longest_trip(int n, int d) {
| ^~~~~~
