#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second map<vector<int>, map<vector<int>, int> > mmm; int query(vector<int> a, vector<int> b){ if (!mmm[a][b]&&!mmm[b][a])mmm[b][a]=mmm[a][b]=are_connected(a, b)+1; return mmm[a][b]-1; } vector<int> longest_trip(int n, int d){ if (d==3){ vector<int> ans; for (int i=0; i<n; ++i)ans.pb(i); return ans; } if (d==2){ deque<int> ans(1, 0); int done=1; if (are_connected({0}, {1}))ans.pb(1); else ans.pb(2), done=2; for (int i=1; i<n; ++i)if (i!=done){ if (are_connected({i}, {ans.back()}))ans.pb(i); else ans.push_front(i); } vector<int> res; for (auto a:ans)res.pb(a); return res; } //vector<int> ord; //for (int i=1; i<n; ++i)ord.pb(i); //mt19937 gen(67); //shuffle(ord.begin(), ord.end(), gen); deque<int> ans(1, 0); set<int> s; for (int i=1; i<n; ++i)s.insert(i); while (s.size()>n/2){ vector<int> temp; for (int a:s){ //int i=ord[a]; int i=a; if (query({i}, {ans.back()})){ ans.pb(i); temp.pb(a); continue; } if (query({i}, {ans[0]})){ ans.push_front(i), temp.pb(a); continue; } if (ans.size()>=4){ ans.insert(ans.begin()+2, i); temp.pb(a); continue; } for (int j=1; j<ans.size(); ++j)if (query({i}, {ans[j-1]})&&query({i}, {ans[j]})){ ans.insert(ans.begin()+j, i); temp.pb(a); break; } } for (auto a:temp)s.erase(a); } vector<int> res; for (auto a:ans)res.pb(a); return res; }