#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> solve_d3(int N, int D)
{
vector<int> res(N);
iota(res.begin(), res.end(), 0);
return res;
}
vector<int> solve_d2(int N, int D)
{
queue<int> stops;
for (int i = 1; i < N; i++)
stops.push(i);
deque<int> trip = {0};
while (stops.size() > 1)
{
int next = stops.front();
stops.pop();
int last = trip.back();
if (are_connected({next}, {last}))
{
trip.push_back(next);
}
else
{
trip.push_back(stops.front());
stops.pop();
trip.push_back(next);
}
}
if (stops.size() == 1)
{
int next = stops.front();
int last = trip.back();
if (are_connected({next}, {last}))
{
trip.push_back(next);
}
else
{
trip.push_front(stops.front());
stops.pop();
}
}
vector<int> res;
for (int x : trip)
res.push_back(x);
return res;
}
int pop(queue<int> &q)
{
int x = q.front();
q.pop();
return x;
}
const bool maybe = true;
map<pair<int, int>, bool> cache;
bool are_conn(vector<int> a, vector<int> b) {
if (a.size() != 1 || b.size() != 1) return are_connected(a, b);
int x = a[0], y = b[0];
if (x < y) swap(x, y);
if (cache.count({x, y})) return cache[{x, y}];
cache[{x, y}] = are_connected(a, b);
return cache[{x, y}];
}
vector<int> longest_trip(int N, int D)
{
if (D == 3)
return solve_d3(N, D);
if (D == 2)
return solve_d2(N, D);
cache.clear();
queue<int> nodes;
for (int i = 0; i < N; i++)
nodes.push(i);
vector<int> a, b;
a.push_back(pop(nodes));
bool ends_connected = maybe;
// false = a and b are not connected
// true = a and b are maybe connected
while (!nodes.empty())
{
if (b.empty())
{
int n = pop(nodes);
if (are_conn({a.back()}, {n}))
{
a.push_back(n);
}
else
{
// missed optimization
// we could cache that a and b are not connected
b.push_back(n);
ends_connected = false;
}
continue;
}
// both a and b are non-empty
int n = pop(nodes);
if (are_conn({a.back()}, {n}))
{
a.push_back(n);
ends_connected = maybe;
}
else if (are_conn({b.back()}, {n}))
{
b.push_back(n);
ends_connected = false;
}
else
{
// ends of a and b are definitely connected
while (!b.empty())
{
a.push_back(b.back());
b.pop_back();
}
assert(b.empty());
b.push_back(n);
}
}
if (b.empty())
{
return a;
}
if (ends_connected == maybe && are_conn({a.back()}, {b.back()}))
{
while (!b.empty())
{
a.push_back(b.back());
b.pop_back();
}
return a;
}
if (!are_conn(a, b))
{
if (a.size() > b.size())
{
return a;
}
else
{
return b;
}
}
if (a.size() < b.size())
swap(a, b);
assert(a.size() >= b.size());
bool a_circle = are_conn({a.front()}, {a.back()});
if (!a_circle)
{
for (int x : a)
b.push_back(x);
return b;
}
// a is a circle
bool b_circle = b.size() == 1 || are_conn({b.front()}, {b.back()});
if (!b_circle) {
for (int x : b) a.push_back(x);
return a;
}
// both a and b are circles
deque<int> A, B;
for (int x : a) A.push_back(x);
for (int x : b) B.push_back(x);
while (true) {
int e = A.front(); A.pop_front();
A.push_back(e);
if (are_conn({e}, b)) break;
}
while (true) {
int e = B.back(); B.pop_back();
B.push_front(e);
if (are_conn({A.back()}, {e})) break;
}
vector<int> res;
for (int x : A) res.push_back(x);
for (int x : B) res.push_back(x);
return res;
}
