#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
map <pair<vector<int>, vector <int> >, int> memo;
bool are(vector <int> a, vector <int> b){
return are_connected(a, b);
sort(a.begin(), a.end());
sort(b.begin(), b.end());
a.erase(unique(a.begin(), a.end()), a.end());
b.erase(unique(b.begin(), b.end()), b.end());
if(memo.find({a, b}) != memo.end()) return memo[{a, b}];
return memo[{a, b}] = are_connected(a, b);
}
vector<int> longest_trip(int n, int d){
srand(time(0));
vector <int> v;
for(int i = 0; i < n; i++) v.push_back(i);
// // int dosta = n * n;
//
// // for(int i = 0; i < dosta; i++){
// // int p1 = rand() % n;
// // int p2 = rand() % n;
//
// // if(p1 != p2) swap(v[p1], v[p2]);
// // }
vector <int> a, b;
a.push_back(v[0]);
for(int i = 1; i < n; i++){
//if(rand() % 2) swap(a, b);
if(are({a.back()}, {v[i]})) a.push_back(v[i]);
else if(b.empty() || are({b.back()}, {v[i]})) b.push_back(v[i]);
else {
while(!b.empty()){
a.push_back(b.back());
b.pop_back();
}
b.push_back(v[i]);
}
}
if(a.size() < b.size()) swap(a, b);
if(a.size() == n) return a;
//if(are({a[0], a.back()}, {b[0], b.back()}))
if(are({a.back()}, {b[0]})){
for(int i = 0; i < b.size(); i++){
a.push_back(b[i]);
}
return a;
}
if(are({a.back()}, {b.back()})){
for(int i = b.size() - 1; i >= 0; i--){
a.push_back(b[i]);
}
return a;
}
if(are({b.back()}, {a[0]})){
for(int i = 0; i < a.size(); i++){
b.push_back(a[i]);
}
return b;
}
if(!are(a, b)) return a;
int lo = 1, hi = a.size();
while(lo < hi){
int mid = (lo + hi) / 2;
v.clear();
for(int i = 0; i < mid; i++){
v.push_back(a[i]);
}
if(are(v, b)) hi = mid;
else lo = mid + 1;
}
v.clear();
for(int i = hi; i < a.size(); i++) v.push_back(a[i]);
for(int i = 0; i < hi; i++) v.push_back(a[i]);
a = v;
lo = 1, hi = b.size();
while(lo < hi){
int mid = (lo + hi) / 2;
v.clear();
for(int i = 0; i < mid; i++){
v.push_back(b[i]);
}
if(are({a.back()}, v)) hi = mid;
else lo = mid + 1;
}
for(int i = hi - 1; i < b.size(); i++) a.push_back(b[i]);
for(int i = 0; i < hi - 1; i++) a.push_back(b[i]);
return a;
}
