#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
vector<ll> longest_trip(int N, int D) {
vector<ll> cnum,ccur; //current vector, current "stack"
queue<ll> rnum; //remaining nums
ll x0 = 0;
cnum.push_back(0);
for (ll i=1;i<N;i++) {
rnum.push(i);
}
while (!rnum.empty()) {
x0 = cnum[cnum.size()-1];
ll x1 = rnum.front(); rnum.pop();
ccur.push_back(x1);
if (are_connected((vector<int>){x0},(vector<int>{x1}))) {
sort(ccur.rbegin(),ccur.rend());
for (ll y: ccur) {
cnum.push_back(y);
}
ccur.clear();
x0 = cnum[cnum.size()-1];
}
}
if (ccur.size()==0) {
return cnum;
}
if (are_connected(ccur,(vector<int>){cnum[0]})) {
vector<ll> vfin = ccur;
for (ll y: cnum) {
vfin.push_back(y);
}
return vfin;
}
if (!are_connected(cnum,ccur)) {
if (cnum.size()<ccur.size()) {
return ccur;
} else {
return cnum;
}
}
ll M = cnum.size();
ll imin = 0; ll imax = M-1;
while (imin<imax) {
ll it = (imin+imax)/2;
vector<ll> vtest;
for (ll j=imin;j<=it;j++) {
vtest.push_back(cnum[j]);
}
if (are_connected(vtest,ccur)) {
imax = it;
} else {
imin = it+1;
}
}
ll it = imin;
vector<ll> vfin = ccur;
for (ll i=0;i<M;i++) {
vfin.push_back(cnum[(i+it)%M]);
}
return vfin;
}
