#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int n, int D) {
if(D==3){
vector<int>ans(n);
iota(ans.begin(),ans.end(),0);
return ans;
}
if(D==2){
set<int>lef;
for(int i = 0;i<n;i++){
lef.insert(i);
}
vector<int>ans;
ans.push_back(0);
lef.erase(0);
while(lef.size()>1){
if(are_connected({ans.back()},{*lef.begin()})){
ans.push_back(*lef.begin());
lef.erase(lef.begin());
}
else{
ans.push_back(*(++lef.begin()));
lef.erase(++lef.begin());
}
}
if(are_connected({*lef.begin()},{ans.back()})){
ans.push_back(*lef.begin());
return ans;
}
ans.insert(ans.begin(),*lef.begin());
return ans;
}
assert(D==1);
vector<int>pt1,pt2;
pt1.push_back(0);
for(int i = 1;i<n;i++){
int prev1 = pt1.back();
if(are_connected({prev1},{i})){
pt1.push_back(i);
continue;
}
//not adjacent.
if(pt2.size()){
int prev2 = pt2.back();
if(are_connected({prev2},{i})){
pt2.push_back(i);
}
else{
reverse(pt2.begin(),pt2.end());
pt1.insert(pt1.end(),pt2.begin(),pt2.end());
pt2.clear();
i--;
continue;
}
}
else{
pt2.push_back(i);
}
}
if(pt2.size()==0){
return pt1;
}
if(!are_connected(pt1,pt2)){
if(pt1.size()>pt2.size()){
return pt1;
}
return pt2;
}
vector<int>t1;
if(pt1.size()==1){
t1.push_back(pt1[0]);
}
else{
t1.push_back(pt1[0]);
t1.push_back(pt1[pt1.size()-1]);
}
vector<int>t2;
if(pt2.size()==1){
t2.push_back(pt2[0]);
}
else{
t2.push_back(pt2[0]);
t2.push_back(pt2[pt2.size()-1]);
}
if(are_connected(t1,t2)){
//ends connected
if(are_connected({pt1[0]},{pt2[0]})){
vector<int>ans;
reverse(pt1.begin(),pt1.end());
for(int i : pt1){
ans.push_back(i);
}
for(int i : pt2){
ans.push_back(i);
}
return ans;
}
//fronts
if(are_connected({pt1[0]},{pt2[pt2.size()-1]})){
vector<int>ans;
for(int i : pt2){
ans.push_back(i);
}
for(int i : pt1){
ans.push_back(i);
}
return ans;
}
if(are_connected({pt1[pt1.size()-1]},{pt2[pt2.size()-1]})){
vector<int>ans;
for(int i : pt1){
ans.push_back(i);
}
reverse(pt2.begin(),pt2.end());
for(int i : pt2){
ans.push_back(i);
}
return ans;
}
if(are_connected({pt1[pt1.size()-1]},{pt2[0]})){
vector<int>ans;
for(int i : pt1){
ans.push_back(i);
}
for(int i : pt2){
ans.push_back(i);
}
return ans;
}
}
//both cycles now.
//must find joiner.
int lo1 = 0;
int hi1 = pt1.size()-1;
while(lo1<hi1){
int mid = (lo1+hi1)/2;
vector<int>quer;
for(int i = 0;i<=mid;i++){
quer.push_back(pt1[i]);
}
if(are_connected(quer,pt2)){
hi1=mid;
}
else{
lo1=mid+1;
}
}
vector<int> new_pt1;
for (int i = 0; i < pt1.size(); i++) {
new_pt1.push_back(pt1[(lo1 + i) % pt1.size()]);
}
int left = 0, right = pt2.size()-1;
while (left < right) {
int mid = (left+right)/2;
vector<int> query_pt2;
for (int i = 0; i <= mid; i++) {
query_pt2.push_back(pt2[i]);
}
if (are_connected({new_pt1[0]}, query_pt2)) {
right = mid;
} else {
left = mid+1;
}
}
int x_index = left;
vector<int> new_pt2;
for (int i = 0; i < pt2.size(); i++) {
new_pt2.push_back(pt2[(x_index + i) % pt2.size()]);
}
new_pt1.insert(new_pt1.end(), new_pt2.begin(), new_pt2.end());
return new_pt1;
}
