#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 = 0;
node *next(node* prev) {
return (node*)(npx ^ (uintptr_t)prev);
}
};
node *head = nullptr, *tail = nullptr;
int size = 0;
xlist(initializer_list<int> list) {
if (list.size() == 0) return;
size = 1;
head = tail = new node{ .storage = *list.begin() };
for (auto it = next(list.begin()); it != list.end(); ++it)
append(*it);
}
xlist(node *head, node* tail, int size) : head(head), tail(tail), size(size) {}
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) {
if (size == 0) {
*this = l;
return;
}
if (l.size == 0)
return;
tail->npx ^= (uintptr_t)l.head;
l.head->npx ^= (uintptr_t)tail;
tail = l.tail;
size += l.size;
l.size = 0;
l.head = l.tail = nullptr;
}
int front() {
return head->storage;
}
int back() {
return tail->storage;
}
void reverse() {
swap(head, tail);
}
vec<int> collect() {
vec<int> res;
node* prev = nullptr;
node* curr = head;
while (curr != nullptr) {
res.push_back(curr->storage);
node* next = curr->next(prev);
prev = curr;
curr = next;
}
return res;
}
array<xlist, 2> cut(int i) {
assert(i < size - 1);
node* prev = nullptr;
node* curr = head; int curr_i = 0;
while (curr_i < i) {
node* next = curr->next(prev);
prev = curr;
curr = next; curr_i++;
}
node* atail = curr;
node* bhead = curr->next(prev);
atail->npx ^= (uintptr_t)bhead;
bhead->npx ^= (uintptr_t)atail;
xlist a(head, atail, i + 1),
b(bhead, tail, size - i - 1);
return {a, b};
}
};
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) // ∂ = 3; (clique scenario)
return nodes;
if (D == 2) { // ∂ = 2 (hamiltonian path constructable)
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());
}
// ∂ = 1; furthur analysis; construct two paths.
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);
}
}
vec<int> p0, p1;
{ // return bigger path if paths aren't connected; (two-clique scenario)
p0 = path[0].collect(); p1 = path[1].collect();
if (!are_connected(p0, p1))
return p0.size() > p1.size() ? p0 : p1;
}
{ // connect paths if endpoints are connected;
bool connected = true;
if (are_connected({path[0].front()}, {path[1].front()})) {
path[0].reverse();
path[0].concat(path[1]);
} else if (are_connected({path[0].front()}, {path[1].back()})) {
path[1].concat(path[0]);
path[0] = path[1];
} else // p1.f <-> p1.b;
connected = false;
if (connected)
return path[0].collect();
connected = true;
if (are_connected({path[0].back()}, {path[1].front()}))
path[0].concat(path[1]);
else if (are_connected({path[0].back()}, {path[1].back()})) {
path[1].reverse();
path[0].concat(path[1]);
} else // p2.f <-> p2.b;
connected = false;
if (connected)
return path[0].collect();
}
int a, b;
{ // find any edge between paths; (using binary-search)
a = 0;
int l = 0, r = (int) p0.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
if (are_connected(vec<int>(p0.begin() + l, p0.begin() + mid + 1), p1))
r = mid;
else
l = mid + 1;
}
a = l;
b = 0;
l = 0; r = (int) p1.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
if (are_connected(p0, vec<int>(p1.begin() + l, p1.begin() + mid + 1)))
r = mid;
else
l = mid + 1;
}
b = l;
assert(are_connected({p0[a]}, {p1[b]}));
}
{ // size of two paths longer than one; (at least one path with size bigger than two; inffered from previous conditions)
if (1 < p0.size() && 1 < p1.size()) {
auto [p0a, p0b] = path[0].cut(a);
auto [p1a, p1b] = path[1].cut(b);
p1a.reverse();
p1b.reverse();
p0b.concat(p0a);
p0b.concat(p1a);
p0b.concat(p1b);
assert(0 < a && a < p0.size() - 1);
assert(0 < b && b < p1.size() - 1);
return p0b.collect();
}
}
{ // one path with size = 1, another with size > 3
if (p0.size() == 1) {
swap(a, b);
swap(path[0], path[1]);
}
auto [pa, pb] = path[0].cut(a);
pb.concat(pa);
pb.append(path[0].front());
return pb.collect();
}
}
