#include "longesttrip.h"
#include <queue>
#include <iostream>
//#include <assert.h>
using namespace std;
#define pb push_back
#define dcerr if(1==0)cerr
vector<int> longest_trip(int n, int d){
vector<int> ans;
if(d==2){
// surely there still exists a round trip...
// why is this screaming linked list :(
vector<int> starts;
if(!are_connected({0}, {n-1})){
starts.pb(0);
}
for(int i=1; i<n; i++){
if(!are_connected({i-1}, {i})){
starts.pb(i);
}
}
if(starts.size()==0){
d=3; // go do the easy case (0,1,2,...)
} else{
// we certainly have breaks somewhere.
starts.pb(starts[0]+n);
bool forwards=false;
for(int j=0; j<starts.size()-1; j++){
forwards = !forwards;
if(forwards){
// forwards
for(int i=starts[j]; i<starts[j+1]; i++){
ans.pb(i%n);
}
} else{
// backwards
for(int i=starts[j+1]-1; i>starts[j]-1; i--){
ans.pb(i%n);
}
}
}
}
}
if(d==3){
for(int i=0; i<n; i++){
ans.pb(i);
}
}
if(d==1){
// the boss fight
vector<int> link(n, -1);
int start1, start2, end1, end2;
int a,b,c;
queue<int> q;
a=are_connected({0}, {1});
b=are_connected({1}, {2});
c=are_connected({0}, {2});
if(a){
start1=0;
link[0]=1;
end1=1;
} else if(b){
start1=1;
link[1]=2;
end1=2;
} else if(c){
start1=0;
link[0]=2;
end1=2;
}
for(int i=0; i<n; i++){
if(i!=start1 && i!=end1){
q.push(i);
}
}
a=-1;b=-1;c=-1;
start2=-1;end2=-1;
while(!q.empty()){
// a
a=end1;
// b
if(start2==-1){
b=q.front();
q.pop();
start2=b;
end2=b;
}
// c
if(c==-1 && !q.empty()){
c=q.front();
q.pop();
}
// at this point: b and c are both real values.
//assert(a!=b);
//assert(b!=c);
//assert(a!=c);
if(are_connected({a}, {b})){
// a-b (join the lists)
link[a]=b;
end1=end2;
a=end2;
start2=-1;
end2=-1;
b=-1;
} else if(c!=-1 && are_connected({a}, {c})){
// a-c (go to list1)
end1=c;
link[a]=c;
c=-1;
} else if(c!=-1){ //|| are_connected({b}, {c})){
// b-c (go to list2)
start2=c;
link[c]=b;
b=c;
c=-1;
}
}
// recall that:
// a = the end of the first string
// b = the start of the second string (possibly -1)
// c = the new value to add (possibly -1)
// if c has a value, then we aren't really done...
if(c != -1){
// we aren't done
// c being something means that b is nothing (!)
if(are_connected({a}, {c})){
link[a]=c;
end1=c;
a=c;
c=-1;
} else{
start2=c;
end2=c;
} // now to append c...
}
// <--- DEBUGGING --->
dcerr<<"start1, end1: "<<start1<<", "<<end1<<"\n";
dcerr<<"start2, end2: "<<start2<<", "<<end2<<"\n";
int cur=start1;
vector<int> ans1={start1};
while(link[cur] != -1){
cur = link[cur];
ans1.pb(cur);
}
if(start2==-1){
return ans1;
} // else...
// in this case we have to do some freaky shit
cur=start2;
vector<int> ans2={start2};
while(link[cur] != -1){
cur = link[cur];
ans2.pb(cur);
}
// ans1+ans2=everything (I hope)
if(!are_connected(ans1, ans2)){
if(ans1.size() >= ans2.size()){
return ans1;
} else{
return ans2;
}
}
dcerr<<"$ they are connected...\n";
// oh shit they're connected...
vector<int> finalanswer;
vector<int> secondary_endpoints = {start2};
if(start2 != end2) secondary_endpoints.pb(end2);
if(are_connected({start1, end1}, secondary_endpoints)){
// simple case.
if(are_connected({end1}, {start2})){
dcerr<<"$ simple case 1.\n";
for(int i=0; i<ans1.size(); i++) finalanswer.pb(ans1[i]);
for(int i=0; i<ans2.size(); i++) finalanswer.pb(ans2[i]);
} else if(are_connected({end1}, {end2})){
for(int i=0; i<ans1.size(); i++) finalanswer.pb(ans1[i]);
for(int i=ans2.size()-1; i>-1; i--) finalanswer.pb(ans2[i]);
} else if(are_connected({start1}, {start2})){
for(int i=ans1.size()-1; i>-1; i--) finalanswer.pb(ans1[i]);
for(int i=0; i<ans2.size(); i++) finalanswer.pb(ans2[i]);
} else{ //start1, end2
for(int i=ans1.size()-1; i>-1; i--) finalanswer.pb(ans1[i]);
for(int i=ans2.size()-1; i>-1; i--) finalanswer.pb(ans2[i]);
}
return finalanswer;
}
dcerr<<"$ not as simple.\n";
// not-simple case. FUUUUUCCKKK
// both lists are cyclic... binary search? idk
int s1=ans1.size(),s2=ans2.size();
// find the link in ans1...
int a1_connector;
// ...using b*nary search (ew)
int l=0, r=s1-1, m=(r+l)/2;
vector<int> curvec(2,0);
for(int i=l; i<=m; i++) curvec.pb(ans1[i]);
while(curvec.size()>1){
if(are_connected({curvec}, {ans2})){
r = m;
} else{
l = m+1;
}
m = (l+r)/2;
curvec.clear();
for(int i=l; i<=m; i++) curvec.pb(ans1[i]);
}
// now we have curvec.size()==1
a1_connector = l;
int a1_nc = curvec[0];
curvec.clear();
// time to find a2_connector.
int a2_connector;
l=0; r=s2-1; m=(r+l)/2;
for(int i=l; i<=m; i++) curvec.pb(ans2[i]);
while(curvec.size()>1){
if(are_connected({curvec}, {a1_nc})){
r = m;
} else{
l = m+1;
}
m = (l+r)/2;
curvec.clear();
for(int i=l; i<=m; i++) curvec.pb(ans2[i]);
}
a2_connector = l;
// now we should have everything we need :)
for(int i=a1_connector+1; i<a1_connector+s1+1; i++){
finalanswer.pb(ans1[i%s1]);
} for(int i=a2_connector; i<a2_connector+s2; i++){
finalanswer.pb(ans2[i%s2]);
}
return finalanswer;
}
return ans;
}
