#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(0);
std::vector<int> longest_trip(int N, int D)
{
vector<int>x, y;
x.push_back({0});
for(int i=1;i<N;i++){
if(y.size()==0){
if(are_connected({i}, {x[0]})){
x.insert(x.begin(),i);
continue;
}
if (are_connected({i}, {x.back()})){
x.push_back(i);
continue;
}
if(!are_connected({i}, x)){
y={i};
continue;
}
int lo=0;
int hi=x.size()-1;
while(lo<hi){
int m=(lo+hi)/2;
vector<int>z;
for(int i=lo;i<=m;i++){
z.push_back(x[i]);
}
if(are_connected(z, {i})){
hi=m;
} else{
lo=m+1;
}
}
vector<int>z;
for(int i=lo+1;i<x.size();i++){
z.push_back(x[i]);
}
for(int i=0;i<=lo;i++){
z.push_back(x[i]);
}
z.push_back(i);
x=z;
continue;
}
if(!are_connected(x,{i})){
y.push_back(i);
continue;
}
if(!are_connected(y,{i})){
x.push_back(i);
continue;
}
int i0=0;
int j0=0;
if(!are_connected({x[0]},i)){
int lo=1;
int hi=x.size()-1;
while(lo<hi){
int m=(lo+hi)/2;
vector<int>z;
for(int i=lo;i<=m;i++){
z.push_back(x[i]);
}
if(are_connected(z, {i})){
hi=m;
} else{
lo=m+1;
}
}
i0=lo;
}
if(!are_connected({y[0]},i)){
int lo=1;
int hi=y.size()-1;
while(lo<hi){
int m=(lo+hi)/2;
vector<int>z;
for(int i=lo;i<=m;i++){
z.push_back(x[i]);
}
if(are_connected(z, {i})){
hi=m;
} else{
lo=m+1;
}
}
j0=lo;
}
swap(x[i0], x.back());
swap(y[j0], y[0]);
x.push_back(i);
for(int i: y){
x.push_back(i);
}
y={};
}
if(x.size()>y.size()){
return x;
} else{
return y;
}
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:39:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=lo+1;i<x.size();i++){
| ~^~~~~~~~~
longesttrip.cpp:59:34: error: could not convert 'i' from 'int' to 'std::vector<int>'
59 | if(!are_connected({x[0]},i)){
| ^
| |
| int
longesttrip.cpp:76:34: error: could not convert 'i' from 'int' to 'std::vector<int>'
76 | if(!are_connected({y[0]},i)){
| ^
| |
| int
