#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>; using vi = vector<ll>;
void stest(vector<ll> v0) {
for (ll i=0;i<(v0.size()-1);i++) {
assert(are_connected((vi){v0[i]},(vi){v0[i+1]}));
}
}
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) {
stest(cnum);
return cnum;
}
if (are_connected(ccur,(vector<int>){cnum[0]})) {
vector<ll> vfin = ccur;
for (ll y: cnum) {
vfin.push_back(y);
}
stest(vfin);
return vfin;
}
if (!are_connected(cnum,ccur)) {
if (cnum.size()<ccur.size()) {
//stest(ccur);
return ccur;
} else {
//stest(cnum);
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 K = ccur.size();
ll jmin = 0; ll jmax = K-1;
while (jmin<jmax) {
ll jt = (jmin+jmax)/2;
vector<ll> vtest;
for (ll j=jmin;j<=jt;j++) {
vtest.push_back(ccur[j]);
}
if (are_connected(vtest,(vector<ll>){cnum[imin]})) {
jmax = jt;
} else {
jmin = jt+1;
}
}
assert(are_connected((vector<ll>){cnum[imin]},(vector<ll>){ccur[jmin]}));
vector<ll> vfin;
for (ll i=1;i<=K;i++) {
vfin.push_back(ccur[(i+jmin)%K]);
}
for (ll i=0;i<M;i++) {
vfin.push_back(cnum[(i+imin)%M]);
}
//stest(vfin);
return vfin;
}
