#include "longesttrip.h"
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <deque>
#include <bits/stdc++.h>
using namespace std;
vector<int>prefix(vector<int>v,int ind){
vector<int>pref;
int i;
for(i=0;i<=ind;++i)
pref.push_back(v[i]);
return pref;
}
vector<int>ocol(vector<int>v,int val){
int i;
int poz=0;
for(i=0;i<(int)v.size();++i)
if(v[i]==val)
poz=i;
vector<int>ans;
for(i=poz-1;i>=0;--i)
ans.push_back(v[i]);
for(i=v.size()-1;i>poz;--i)
ans.push_back(v[i]);
return ans;
}
std::vector<int> longest_trip(int N, int D){
if(D==3){
int i;
vector<int>path;
for(i=0;i<N;++i)
path.push_back(i);
return path;
}
else if(D==2){
int i;
deque<int>path;
int vec0;
if(are_connected({0},{1}))
vec0=1;
else
vec0=2;
path.push_back(0);
path.push_back(vec0);
for(i=1;i<N;++i)
if(i!=vec0){
if(are_connected({path.front()},{i}))
path.push_front(i);
else
path.push_back(i);
}
vector<int>ans;
for(auto el : path)
ans.push_back(el);
return ans;
}
else{
vector<int>unu,doi;
int i;
vector<int>perm;
for(i=0;i<N;++i)
perm.push_back(i);
srand(time(0));
for(i=1;i<N;++i){
int sch=rand()%(i+1);
swap(perm[i],perm[sch]);
}
unu.push_back(perm[0]);
int ifor;
for(ifor=1;ifor<N;++ifor){
i=perm[ifor];
if(doi.empty()){
if(are_connected({unu.back()},{i}))
unu.push_back(i);
else
doi.push_back(i);
}
else{
if(rand()%2==0)
swap(unu,doi);
if(!are_connected({unu.back()},{i}))
doi.push_back(i);
else{
if(!are_connected({doi.back()},{i}))
unu.push_back(i);
else{
unu.push_back(i);
reverse(doi.begin(),doi.end());
for(auto el : doi)
unu.push_back(el);
doi.clear();
}
}
}
}
if(doi.empty())
return unu;
if(!are_connected(unu,doi)){
if(unu.size()<doi.size())
swap(unu,doi);
return unu;
}
if(are_connected({unu.front()},{doi.front()})){
reverse(unu.begin(),unu.end());
for(auto el : doi)
unu.push_back(el);
return unu;
}
if(are_connected({unu.front()},{doi.back()})){
reverse(unu.begin(),unu.end());
reverse(doi.begin(),doi.end());
for(auto el : doi)
unu.push_back(el);
return unu;
}
if(are_connected({unu.back()},{doi.front()})){
for(auto el : doi)
unu.push_back(el);
return unu;
}
/// (]
int st=-1,dr=unu.size()-1;
while(dr-st>1){
int mij=(st+dr)/2;
if(are_connected(prefix(unu,mij),doi))
dr=mij;
else
st=mij;
}
vector<int>unu_nod;
unu_nod.push_back(unu[dr]);
st=-1,dr=doi.size()-1;
while(dr-st>1){
int mij=(st+dr)/2;
if(are_connected(prefix(doi,mij),unu_nod))
dr=mij;
else
st=mij;
}
vector<int>rasp;
vector<int>part;
part=ocol(unu,unu_nod[0]);
for(auto el : part)
rasp.push_back(el);
rasp.push_back(unu_nod[0]);
rasp.push_back(doi[dr]);
part=ocol(doi,doi[dr]);
for(auto el : part)
rasp.push_back(el);
return rasp;
}
}
