#include "longesttrip.h"
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
vector<int> longest_trip(int N, int D)
{
vector<int> ans;
vector<int> a = { 0 }, b = { 1 };
for (int i = 2; i < N; i++)
{
if (are_connected({ a.back() }, { i }))
{
a.push_back(i);
}
else if (are_connected({ b.back() }, { i }))
{
b.push_back(i);
}
else
{
for (int j = b.size() - 1; j >= 0; j--)
{
a.push_back(b[j]);
}
b.clear();
b.push_back(i);
}
}
if (are_connected(a, b))
{
if (are_connected({ a[0] }, { a.back() }))
{
if (b.size() != 1)
{
if (!are_connected({ b[0] }, { b.back() }))
{
if (are_connected({ a.back() }, { b[0] }))
{
reverse(b.begin(), b.end());
while (!b.empty())
{
a.push_back(b.back());
b.pop_back();
}
}
else
{
while (!b.empty())
{
a.push_back(b.back());
b.pop_back();
}
}
return a;
}
}
int aket = 0;
int l = 0, r = a.size() - 1;
while (l <= r)
{
vector<int> harc;
int m = (l + r) / 2;
for (int bl = l; bl <= m; bl++)
{
harc.push_back(a[bl]);
}
if (are_connected(harc, b))
{
aket = m;
r = m - 1;
}
else
{
l = m + 1;
}
}
if (b.size() == 1)
{
vector<int> tazaans = {b[0]};
for (int i = aket; i < a.size(); i++)
{
tazaans.push_back(a[i]);
}
for (int i = 0; i < aket; i++)
{
tazaans.push_back(a[i]);
}
return tazaans;
}
int bket = 0;
l = 0, r = b.size() - 1;
while (l <= r)
{
vector<int> harc;
int m = (l + r) / 2;
for (int bl = l; bl <= m; bl++)
{
harc.push_back(b[bl]);
}
if (are_connected(harc, a))
{
bket = m;
r = m - 1;
}
else
{
l = m + 1;
}
}
vector<int> tazaans;
for (int i = aket; i < a.size(); i++)
{
tazaans.push_back(a[i]);
}
for (int i = 0; i < aket; i++)
{
tazaans.push_back(a[i]);
}
for (int i = bket; i < b.size(); i++)
{
tazaans.push_back(b[i]);
}
for (int i = 0; i < bket; i++)
{
tazaans.push_back(b[i]);
}
return tazaans;
}
else
{
if (are_connected({ a.back()},{ b[0] }))
{
reverse(b.begin(), b.end());
while (!b.empty())
{
a.push_back(b.back());
b.pop_back();
}
}
else
{
while (!b.empty())
{
a.push_back(b.back());
b.pop_back();
}
}
return a;
}
}
else
{
if (a.size() < b.size())swap(a, b);
return a;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |