#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; } int queryd(deque<int> aa, deque<int> bb){ vector<int> a, b; for (auto c:aa)a.pb(c); for (auto c:bb)b.pb(c); 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){ mmm.clear(); 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=0; i<n; ++i)ord.pb(i); srand(time(0)); random_shuffle(ord.begin(), ord.end()); deque<int> a(1, ord[0]), b(1, ord[1]); for (int j=2; j<n; ++j){ int i=ord[j]; if (query({i}, {a.back()}))a.pb(i); else if (query({i}, {b.back()}))b.pb(i); else{ while (b.size())a.pb(b.back()), b.pop_back(); b.pb(i); } } if (b.size()>a.size())swap(a, b); if (query({a.back()}, {b.back()})){ while (b.size())a.pb(b.back()), b.pop_back(); } else if (query({a.back()}, {b[0]})){ for (auto c:b)a.pb(c); } else if (query({a[0]}, {b.back()})){ while (b.size())a.push_front(b.back()), b.pop_back(); } else if (query({a[0]}, {b[0]})){ for (auto c:b)a.push_front(c); } else if (queryd(a, b)){ int low=-1, high=a.size()-1; while (low+1<high){ int mid=(low+high)/2; deque<int> temp; for (int i=low+1; i<=mid; ++i)temp.pb(a[i]); if (queryd(temp, b))high=mid; else low=mid; } int froma=high; low=-1, high=b.size()-1; while (low+1<high){ int mid=(low+high)/2; vector<int> temp; for (int i=low+1; i<=mid; ++i)temp.pb(b[i]); if (query({a[froma]}, temp))high=mid; else low=mid; } vector<int> res; for (int p=0; p<a.size(); ++p)res.pb(a[(p+froma+1)%a.size()]); for (int p=0; p<b.size(); ++p)res.pb(b[(p+high)%b.size()]); return res; } vector<int> res; for (auto c:a)res.pb(c); return res; }

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:49:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   49 |         random_shuffle(ord.begin(), ord.end());
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from longesttrip.cpp:2:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~