#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
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) {
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;
}
}
