This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "longesttrip.h"
#define pb push_back
using namespace std;
// Find the first posiion i such that v[i] is connected to i
int find_position(vector<int>& v, int i)
{
int l = 0;
int r = v.size();
while (l + 1 < r) {
int mid = (l + r) / 2;
if (are_connected(vector<int>(v.begin(), v.begin() + mid + 1), {i})) {
r = mid;
}
else {
l = mid;
}
}
return l;
}
vector<int> longest_trip(int N, int D)
{
vector<int> v1, v2;
v1.push_back(0);
for (int i = 1; i < N; i++) {
if (are_connected(v1, {i})) {
if (v2.size()) {
if (are_connected(v2, {i})) {
int p1 = find_position(v1, i);
int p2 = find_position(v2, i);
v1.insert(v1.begin(), v1.begin() + p1, v1.end());
v1.erase(v1.begin() + p1, v1.end());
v1.pb(i);
v1.insert(v1.end(), v2.begin() + p2, v2.end());
v1.insert(v1.end(), v2.begin(), v2.begin() + p2);
v2.clear();
}
else {
v1.pb(i);
}
}
else {
if (are_connected({v1.back()}, {i})) {
v1.pb(i);
}
else {
int p = find_position(v1, i);
v1.insert(v1.end(), v1.begin(), v1.begin() + p);
v1.erase(v1.begin(), v1.begin() + p);
v1.insert(v1.begin(), i);
}
}
}
else {
v2.pb(i);
}
}
if (v1.size() > v2.size()) {
return v1;
}
else {
return v2;
}
}
# | 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... |