#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
int fn(int node, set<int> lefts){
vector<int> left;
for(auto thing:lefts)left.push_back(thing);
int m=left.size();
int cr=0;
for(int i = 8;i>=0;i--){
int ncr=cr|(1<<i);
if(ncr>m)continue;
vector<int> tt;
for(int j = 0;j<ncr;j++)tt.push_back(left[j]);
bool as=are_connected({node}, tt);
if(!as)cr=ncr;
}
if(cr==m || !are_connected({node}, {left[cr]}))return -1;
else return left[cr];
}
int fnd(int node, deque<int> lefts){
vector<int> left;
for(auto thing:lefts)left.push_back(thing);
int m=left.size();
int cr=0;
for(int i = 8;i>=0;i--){
int ncr=cr|(1<<i);
if(ncr>m)continue;
vector<int> tt;
for(int j = 0;j<ncr;j++)tt.push_back(left[j]);
bool as=are_connected({node}, tt);
if(!as)cr=ncr;
}
if(cr==m || !are_connected({node}, {left[cr]}))return -1;
else return left[cr];
}
vector<int> longest_trip(int N, int D){
if(D==3){
vector<int> tt;
for(int i = 0;i<N;i++)tt.push_back(i);
return tt;
}
if(D==2){
int cur=0;
vector<int> res = {cur};
set<int> left;
for(int i = 1;i<N;i++)left.insert(i);
for(int i=0;i<N-2;i++){
int f=*(left.begin());
int s=*(++left.begin());
if(are_connected({cur}, {f})){
left.erase(f);
res.push_back(f);
cur=f;
}
else{
left.erase(s);
res.push_back(s);
cur=s;
}
}
auto last=*(left.begin());
if(are_connected({res.back()},{last})){
res.push_back(last);
return res;
}
else{
auto t1=res.back();
res.pop_back();
auto t2=res.back();
res.pop_back();
res.push_back(t1);
res.push_back(t2);
res.push_back(last);
return res;
}
}
//finished special cases
/*
could get 40 more points with smth trivial
cuz D=1 at least
so finding longest path is easier i think
oh ok algo for tc3 trivial
*/
deque<int> cur={0};
set<int> left;
for(int i = 1;i<N;i++)left.insert(i);
while(cur.size()<N){
auto top=cur.back();
auto nx=fn(top, left);
if(nx!=-1){
cur.push_back(nx);
left.erase(nx);
}
else{
vector<int> blob;
for(auto thing:left)blob.push_back(thing);
if(cur.size()==1){
vector<int> ans;
for(int i = 1;i<N;i++)ans.push_back(i);
return ans;
}
auto ac=are_connected({top}, {cur[0]});
if(!ac){
vector<int> ans=blob;
for(auto thing:cur)ans.push_back(thing);
return ans;
}
else{
for(int i = 0;i<cur.size();i++){
if(are_connected({blob[0]}, {cur[i]})){
vector<int> ans=blob;
reverse(all(ans));
for(int j = i;j<cur.size();j++)ans.push_back(cur[j]);
for(int j = 0;j<i;j++)ans.push_back(cur[j]);
return ans;
}
}
for(int i = 0;i<blob.size();i++){
int nx=fnd(blob[i], cur);
if(nx!=-1){
vector<int> ans;
for(int j = 0;j<blob.size();j++){
if(j!=i)ans.push_back(blob[j]);
}
ans.push_back(blob[i]);
ans.push_back(nx);
for(auto thing:cur){
if(thing!=nx)ans.push_back(thing);
}
return ans;
}
}
if(blob.size()>cur.size())return blob;
else{
vector<int> ans;
for(auto thing:cur)ans.push_back(thing);
return ans;
}
}
}
}
vector<int> ans;
for(auto thing:cur)ans.push_back(thing);
return ans;
}
