#include "longesttrip.h"
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
using pii = pair<int,int>;
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x),end(x)
std::vector<int> longest_trip(int N, int D)
{
map<pii,bool> mp;
auto asktwo = [&](int a,int b){
if(a > b) swap(a,b);
if(mp.count({a,b})) return mp[{a,b}];
else return mp[{a,b}] = are_connected({a},{b});
};
if(D == 3){
vector<int> vc;
for(int i{};i < N;i++){
vc.emplace_back(i);
}
return vc;
}
else{
vector<int> vc[2];
vc[0].emplace_back(0);
vc[1].emplace_back(1);
bool justadd2 = 0;
int justconnect = -1;
for(int i{2};i < N;i++){
if(justconnect != -1){
if(asktwo(i,vc[1].back())){
vc[1].emplace_back(i);
}
else{
vector<int> temp;
for(auto k:vc[0]){
temp.emplace_back(k);
if(k == justconnect){
temp.emplace_back(i);
}
}
vc[0] = temp;
}
justconnect = -1;
justadd2 = 0;
}
else if(asktwo(vc[0].back(),i)){
vc[0].emplace_back(i);
justadd2 = 0;
}
else if(justadd2){
vc[1].emplace_back(i);
justadd2 = 0;
}
else{
if(asktwo(vc[1].back(),i)){
vc[1].emplace_back(i);
justadd2 = 1;
}
else{
justconnect = vc[0].back();
reverse(all(vc[1]));
for(auto k:vc[1]) vc[0].emplace_back(k);
vc[1].clear();
vc[1].emplace_back(i);
}
}
// for(auto k:vc[0]) cout << k << " ";
// cout << endl;
// for(auto k:vc[1]) cout << k << " ";
// cout << endl;
// cout << "______" << endl;
}
if(!are_connected(vc[0],vc[1])){
if(vc[0].size() >= vc[1].size()) return vc[0];
else return vc[1];
}
bool willuse;
if(vc[0].size() == 1 && vc[1].size() == 1){
willuse = are_connected({vc[0].back()},{vc[1].back()});
}
else if(vc[0].size() == 1){
willuse = are_connected({vc[0].back()},{vc[1].back(),vc[1].front()});
}
else if(vc[1].size() == 1){
willuse = are_connected({vc[0].back(),vc[0].front()},{vc[1].back()});
}
else{
willuse = are_connected({vc[0].back(),vc[0].front()},{vc[1].back(),vc[1].front()});
}
//cout << willuse << endl;
if(willuse){
if(asktwo(vc[0].back(),vc[1].back())){
reverse(all(vc[1]));
for(auto k:vc[1]) vc[0].emplace_back(k);
return vc[0];
}
if(asktwo(vc[0].back(),vc[1].front())){
for(auto k:vc[1]) vc[0].emplace_back(k);
return vc[0];
}
if(asktwo(vc[0].front(),vc[1].back())){
reverse(all(vc[0]));
reverse(all(vc[1]));
for(auto k:vc[1]) vc[0].emplace_back(k);
return vc[0];
}
if(asktwo(vc[0].front(),vc[1].front())){
reverse(all(vc[0]));
for(auto k:vc[1]) vc[0].emplace_back(k);
return vc[0];
}
}
int l = 0;
int r = vc[0].size()-1;
int p1 = r;
while(l <= r){
int md = l+(r-l)/2;
vector<int> temp;
for(int i{l};i <= md;i++){
temp.emplace_back(vc[0][i]);
}
if(are_connected(temp,vc[1])) p1 = min(p1,md), r = md-1;
else l = md+1;
}
l = 0;
r = vc[1].size()-1;
int p2 = r;
while(l <= r){
int md = l+(r-l)/2;
vector<int> temp;
for(int i{l};i <= md;i++){
temp.emplace_back(vc[1][i]);
}
// for(auto k:temp) cout << k << " ";
//cout << endl;
if(are_connected(temp,{vc[0][p1]})) p2 = min(p2,md), r = md-1;
else l = md+1;
}
//cout << vc[0][p1] << " " << vc[1][p2] << endl;
// cout << "KKKK" << endl;
// cout << p1 << endl;
vector<int> ans;
for(int i{p1+1};i < vc[0].size();i++){
ans.emplace_back(vc[0][i]);
}
for(int i{};i <= p1;i++){
ans.emplace_back(vc[0][i]);
}
for(int i{p2};i < vc[1].size();i++){
ans.emplace_back(vc[1][i]);
}
for(int i{};i < p2;i++){
ans.emplace_back(vc[1][i]);
}
return ans;
}
return vector<int>{};
}
