#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> memo;
int point_query(int a, int b){
if(memo[a][b] != -1) return memo[a][b];
for(int c = 0; c < memo.size(); c++){
if(a == c) continue;
if(b == c) continue;
if(memo[a][c] == 0 && memo[b][c] == 0)
return memo[a][b] = memo[b][a] = 1;
}
return memo[a][b] = memo[b][a] = are_connected({a}, {b});
}
bool merge_paths(vector<int> p1, vector<int> p2, vector<int> &path){
if(p1.size() < p2.size()) swap(p1, p2);
int a = p1[0], b = p1.back();
int c = p2[0], d = p2.back();
vector<int> ends_p1, ends_p2;
if(a == b) ends_p1 = {a};
else ends_p1 = {a,b};
if(c == d) ends_p2 = {c};
else ends_p2 = {c,d};
if(!are_connected(ends_p1, ends_p2)) return false;
if(point_query(a, d)){
path = p2;
path.insert(path.end(), p1.begin(), p1.end());
return true;
}
if(point_query(b, d)){
path = p1;
path.insert(path.end(), p2.rbegin(), p2.rend());
return true;
}
reverse(p2.begin(), p2.end());
d = p2.back();
if(point_query(a, d)){
path = p2;
path.insert(path.end(), p1.begin(), p1.end());
return true;
}
return false;
}
bool merge_cycles(vector<int> c1, vector<int> c2, vector<int> &path){
int a = -1, b = -1;
if(c1.size() > c2.size()) swap(c1, c2);
int n = c1.size(), m = c2.size();
int left = 0, right = m;
while(left + 1 < right){
int mid = (left + right) / 2;
vector<int> c = c2; c.resize(mid);
if(are_connected(c1, c)) right = mid;
else left = mid;
}
b = right-1;
if(b == -1) return false;
left = 0, right = n;
while(left + 1 < right){
int mid = (left + right) / 2;
vector<int> c = c1; c.resize(mid);
if(are_connected({c2[b]}, c)) right = mid;
else left = mid;
}
a = right-1;
for(int i = (a + 1) % n; i != a; i = (i+1)%n) path.push_back(c1[i]);
path.push_back(c1[a]);
path.push_back(c2[b]);
for(int i = (b + 1) % m; i != b; i = (i+1)%m) path.push_back(c2[i]);
return true;
}
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){
deque<int> ans;
int start = 3;
if(are_connected({0}, {1}))
ans = {0, 1}, start = 2;
else
ans = {0, 2, 1};
for(int v = start; v < N; v++){
if(are_connected({ans.front()}, {v})) ans.push_front(v);
else ans.push_back(v);
}
return {ans.begin(), ans.end()};
}
if(D == 1){
memo = vector<vector<int>>(N, vector<int>(N, -1));
vector<vector<int>> ans = {{0}, {1}};
vector<int> vert(N-2); iota(vert.begin(), vert.end(), 2);
for(int v : vert){
int a = ans[0].back();
int b = ans[1].back();
if(point_query(a, v)){
ans[0].push_back(v);
} else if(point_query(b, v))
ans[1].push_back(v);
else{
ans[0].insert(ans[0].end(), ans[1].rbegin(), ans[1].rend());
ans[1] = {v};
}
}
vector<int> path;
if(!are_connected(ans[0], ans[1])){
if(ans[0].size() > ans[1].size()) return ans[0];
return ans[1];
}
if(merge_paths(ans[0], ans[1], path))
return path;
if(merge_cycles(ans[0], ans[1], path))
return path;
}
return {};
}
