#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();
srand(time(0));
vector<int> rand_nodes(N);
iota(rand_nodes.begin(), rand_nodes.end(), 0);
random_shuffle(rand_nodes.begin(), rand_nodes.end());
queue<int> nodes;
for (int x : rand_nodes)
nodes.push(x);
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_d, B;
// for (int x : a) A_d.push_back(x);
// for (int x : b) B.push_back(x);
// while (true) {
// int e = A_d.front(); A_d.pop_front();
// A_d.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_d.back()}, {e})) break;
// }
// vector<int> res;
// for (int x : A_d) res.push_back(x);
// for (int x : B) res.push_back(x);
// return res;
// both a and b are circles
// there is atleast one edge between a and b
int a_connect;
vector<int> x, y, A_d;
for (int i: a) A_d.push_back(i);
while (A_d.size() > 1) {
x.clear();
y.clear();
for (int i = 0; i < A_d.size(); i++) {
if (i % 2 == 0) x.push_back(A_d[i]);
else y.push_back(A_d[i]);
}
if (are_conn(x, b)) { // the connection is in x
A_d = x;
} else {
A_d = y;
}
}
assert(A_d.size() == 1);
a_connect = A_d[0];
x.clear();
y.clear();
vector<int> B;
int b_connect;
for (int i: b) B.push_back(i);
while (B.size() > 1) {
x.clear();
y.clear();
for (int i = 0; i < B.size(); i++) {
if (i % 2 == 0) x.push_back(B[i]);
else y.push_back(B[i]);
}
if (are_conn({a_connect}, x)) { // the connection is in x
B = x;
} else {
B = y;
}
}
assert(B.size() == 1);
b_connect = B[0];
deque<int> A_d, B_d;
for (int x : a) A_d.push_back(x);
for (int x : b) B_d.push_back(x);
while (true) {
A_d.push_back(A_d.front());
A_d.pop_front();
if (A_d.back() == a_connect) break;
}
while (true) {
B_d.push_front(B_d.back());
B_d.pop_back();
if (B_d.front() == b_connect) break;
}
vector<int> res;
for (int x: A_d) res.push_back(x);
for (int x: B_d) res.push_back(x);
return res;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:233:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
233 | for (int i = 0; i < A_d.size(); i++) {
| ~~^~~~~~~~~~~~
longesttrip.cpp:257:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
257 | for (int i = 0; i < B.size(); i++) {
| ~~^~~~~~~~~~
longesttrip.cpp:273:16: error: conflicting declaration 'std::deque<int, std::allocator<int> > A_d'
273 | deque<int> A_d, B_d;
| ^~~
longesttrip.cpp:226:23: note: previous declaration as 'std::vector<int> A_d'
226 | vector<int> x, y, A_d;
| ^~~
longesttrip.cpp:279:13: error: 'class std::vector<int>' has no member named 'pop_front'
279 | A_d.pop_front();
| ^~~~~~~~~
