#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
mt19937_64 rnd(time(0));
using vi = vector<int>;
vi mrg(const vi&a, const vi&b) {
vi c = a;
for(int x : b) c.push_back(x);
return c;
}
vector<int> longest_trip(int n, int d)
{
deque<vi> pths;
auto add_back =[&](const vi&v) {
if(v.size()==1)pths.push_back(v);
else pths.push_front(v);
};
for(int i=0;i<n;i++)add_back({i});
shuffle(pths.begin(),pths.end(), rnd);
while(pths.size()>2){
auto v1 = pths.back();
pths.pop_back();
auto v2 = pths.back();
pths.pop_back();
if(are_connected({v1[0]}, {v2[0]})) {
reverse(all(v1));
auto v = mrg(v1,v2);
add_back(v);
}
else {
int no1 = 1, no2 = 1;
if(v1.size()==1)no1=2;
if(v2.size()==1)no2=2;
while(no1&&no2&&pths.size()){
auto v3 = pths.front();
pths.pop_front();
if(are_connected({v1[0]}, {v3[0]})){
reverse(all(v1));
v1 = mrg(v1,v3);
no1--;
}
else {
reverse(all(v2));
v2 = mrg(v2,v3);
no2--;
}
}
add_back(v1);
add_back(v2);
}
}
if(pths.size()==1)return pths[0];
auto v1 = pths[0], v2 = pths[1];
if(are_connected({v1[0]},{v2[0]})){
reverse(all(v2));
return mrg(v2,v1);
}
if(are_connected({v1[0]},{v2.back()})){
return mrg(v2,v1);
}
auto bsearch = [](vi v1, vi v2) {
int l=0,r=v2.size()-1;
while(l<r){
// cerr << "bs " << l << " " << r << endl;
int mid = (l+r)/2;
vi sv {v2.begin()+l,v2.begin()+mid+1};
if(are_connected(v1,sv)){
r=mid;
}
else {
l=mid+1;
}
}
return l;
};
if(are_connected({v1[0]},v2)){
int ind2 = bsearch({v1[0]},v2);
// cerr << "R1 " << ind2 << endl;
rotate(v2.begin(),v2.begin()+ind2,v2.end());
reverse(all(v1));
return mrg(v1,v2);
}
if(are_connected({v1.back()},{v2[0]})){
return mrg(v1,v2);
}
swap(v1,v2);
if(are_connected({v1[0]},v2)){
int ind2 = bsearch({v1[0]},v2);
rotate(v2.begin(),v2.begin()+ind2,v2.end());
reverse(all(v1));
return mrg(v1,v2);
}
if(are_connected(v1,v2)){
int ind2 = bsearch(v1,v2);
int ind1 = bsearch({v2[ind2]}, v1);
// cerr << ind1 << " " << ind2 << endl;
rotate(v1.begin(),v1.begin()+ind1,v1.end());
// cerr << "rotate1" << endl;
rotate(v2.begin(),v2.begin()+ind2,v2.end());
reverse(all(v1));
return mrg(v1,v2);
}
return v1.size() > v2.size() ? v1 : v2;
}
