#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;
vector<int> longest_trip(int N, int D) {
if (D == 3) return solve_d3(N, D);
if (D == 2) return solve_d2(N, D);
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_connected({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_connected({a.back()}, {n})) {
a.push_back(n);
ends_connected = maybe;
} else if (are_connected({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_connected({a.back()}, {b.back()})) {
while(!b.empty()) {
a.push_back(b.back());
b.pop_back();
}
return a;
}
if (!are_connected(a, b)) {
if (a.size() > b.size()) {
return a;
} else {
return b;
}
}
// not finished
if (a.size() > b.size()) {
return a;
} else {
return b;
}
}
