#include "longesttrip.h"
#include <bits/stdc++.h>
template<typename T>
using vec = std::vector<T>;
using namespace std;
struct xlist {
struct node {
int storage;
uintptr_t npx;
};
node *head = nullptr, *tail = nullptr;
int size = 0;
xlist(initializer_list<int> list) {
size = (int) list.size();
if (list.size() == 0) return;
head = tail = new node{ .storage = *list.begin() };
for (auto it = next(list.begin()); it != list.end(); ++it)
append(*it);
}
void append(int a) {
if (size == 0) {
*this = xlist{a};
return;
}
node *t = new node{ .storage = a };
t->npx = (uintptr_t)tail;
tail->npx ^= (uintptr_t)t;
tail = t;
size++;
}
void concat(xlist &l) {
tail->npx ^= (uintptr_t)l.head;
l.head->npx ^= (uintptr_t)tail;
tail = l.head;
size += l.size;
l.size = 0;
l.head = l.tail = nullptr;
}
int back() {
return tail->storage;
}
void reverse() {
swap(head, tail);
}
vec<int> collect() {
vec<int> res;
uintptr_t prev = 0;
node* curr = head;
while (curr != 0) {
res.push_back(curr->storage);
uintptr_t next = curr->npx ^ prev;
prev = (uintptr_t) curr;
curr = (node*)next;
}
return res;
}
};
std::vector<int> longest_trip(int N, int D)
{
vec<int> nodes(N); for (int i = 0; i < N; i++) nodes[i] = i;
if (D == 3)
return nodes;
if (D == 2) {
deque<int> path{0, are_connected({0}, {1}) ? 1 : 2};
nodes.erase(find(nodes.begin(), nodes.end(), path.front()));
nodes.erase(find(nodes.begin(), nodes.end(), path.back()));
while (!nodes.empty()) {
auto u = nodes.back(); nodes.pop_back();
if (are_connected({path.front()}, {u}))
path.push_front(u);
else
path.push_back(u);
}
return vec<int>(path.begin(), path.end());
}
xlist path[2] = {{0}, {1}};
nodes.erase(find(nodes.begin(), nodes.end(), path[0].back()));
nodes.erase(find(nodes.begin(), nodes.end(), path[1].back()));
while (!nodes.empty()) {
auto u = nodes.back(); nodes.pop_back();
if (are_connected({path[0].back()}, {u}))
path[0].append(u);
else if (are_connected({path[1].back()}, {u}))
path[1].append(u);
else {
path[1].reverse();
path[0].concat(path[1]);
path[1].append(u);
}
}
return (path[0].size > path[1].size ? path[0] : path[1]).collect();
}
