#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
const int N = 256;
int n, d;
int store[N][N];
bool query(vector<int> a, vector<int> b){
if (a.empty() or b.empty()) return 0;
if (a.size() > 1 or b.size() > 1)
return are_connected(a, b);
if (store[a[0]][b[0]]) return store[a[0]][b[0]] - 1;
bool res = are_connected(a, b);
store[a[0]][b[0]] = 1 + res;
return res;
}
vector<int> longest_trip(int nn, int dd){
n = nn, d = dd;
vector<int> res;
if (d > 1){
deque<int> dq;
if (query({0}, {1})){
dq.push_back(0), dq.push_back(1);
for (int i = 2; i < n; i ++){
if (query({dq.back()}, {i}))
dq.push_back(i);
else
dq.push_front(i);
}
for (int x : dq)
res.push_back(x);
return res;
}
dq.push_back(0); dq.push_back(2); dq.push_back(1);
for (int i = 3; i < n; i ++){
if (query({dq.back()}, {i}))
dq.push_back(i);
else
dq.push_front(i);
}
for (int x : dq)
res.push_back(x);
return res;
}
vector<int> chain1, chain2;
chain1.push_back(0);
for (int i = 1; i < n; i ++){
if (query({chain1.back()}, {i})){
chain1.push_back(i);
continue;
}
if (chain2.empty() or query({chain2.back()}, {i})){
chain2.push_back(i);
continue;
}
reverse(chain2.begin(), chain2.end());
for (int x : chain2)
chain1.push_back(x);
chain2 = {i};
}
if (!query(chain1, chain2)){
if (chain1.size() > chain2.size()) return chain1;
return chain2;
}
if (query({chain1[0]}, {chain2.back()})){
for (int x : chain1) chain2.push_back(x);
return chain2;
}
if (query({chain1.back()}, {chain2.back()})){
reverse(chain2.begin(), chain2.end());
for (int x : chain2) chain1.push_back(x);
return chain1;
}
if (query({chain2[0]}, {chain1[0]})){
reverse(chain2.begin(), chain2.end());
for (int x : chain1) chain2.push_back(x);
return chain2;
}
if (query({chain2[0]}, {chain1.back()})){
for (int x : chain2) chain1.push_back(x);
return chain1;
}
int l = -1, r = chain1.size() - 1;
while (r - l > 1){
int mid = (l + r) / 2;
vector<int> vec;
for (int i = 0; i <= mid; i ++)
vec.push_back(chain1[i]);
if (query(vec, chain2)) r = mid;
else l = mid;
}
vector<int> vec;
for (int i = 0; i <= r; i ++)
vec.push_back(chain1[i]);
int P = r;
l = -1, r = chain2.size() - 1;
while (r - l > 1){
int mid = (l + r) / 2;
vector<int> vec2;
for (int i = 0; i <= mid; i ++)
vec2.push_back(chain2[i]);
if (query(vec2, vec)) r = mid;
else l = mid;
}
vector<int> vec2;
for (int i = 0; i <= r; i ++)
vec2.push_back(chain2[i]);
int Q = r;
for (int i = P + 1; i < chain1.size(); i ++)
res.push_back(chain1[i]);
for (int i = 0; i <= P; i ++)
res.push_back(chain1[i]);
for (int i = Q; i < chain2.size(); i ++)
res.push_back(chain2[i]);
for (int i = 0; i < Q; i ++)
res.push_back(chain2[i]);
return res;
}
