#include "longesttrip.h"
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
bool find_edge(int a, int b) {
return are_connected({ a }, { b });
}
vector <int> longest_trip(int n, int d) {
vector <int> perm(n);
for (int i = 0; i < n; i++) {
perm[i] = i;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(perm.begin(), perm.end(), rng);
vector <int> p1, p2;
p1.push_back(perm[0]);
p2.push_back(perm[1]);
for (int i = 2; i < n - 1; i++) {
int a = perm[i], b = perm[i + 1];
if (find_edge(a, b)) {
if (find_edge(p1.back(), a)) {
p1.push_back(a);
p1.push_back(b);
}
else if (find_edge(p2.back(), a)) {
p2.push_back(a);
p2.push_back(b);
}
else {
while (!p2.empty()) {
p1.push_back(p2.back());
p2.pop_back();
}
p2.push_back(a);
p2.push_back(b);
}
}
else {
if (find_edge(p1.back(), a)) p1.push_back(a);
else {
p1.push_back(b);
b = a;
}
if (find_edge(p2.back(), b)) {
p2.push_back(b);
}
else {
while (!p2.empty()) {
p1.push_back(p2.back());
p2.pop_back();
}
p2.push_back(b);
}
}
}
if (n % 2 == 1) {
int a = perm.back();
if (find_edge(p1.back(), a)) {
p1.push_back(a);
}
else if (find_edge(p2.back(), a)) {
p2.push_back(a);
}
else {
while (!p2.empty()) {
p1.push_back(p2.back());
p2.pop_back();
}
p2.push_back(a);
}
}
if (find_edge(p1[0], p2[0])) {
vector <int> ans;
reverse(p1.begin(), p1.end());
for (auto& it : p1) {
ans.push_back(it);
}
for (auto& it : p2) {
ans.push_back(it);
}
return ans;
}
if (find_edge(p1[0], p2.back())) {
vector <int> ans;
reverse(p1.begin(), p1.end());
reverse(p2.begin(), p2.end());
for (auto& it : p1) {
ans.push_back(it);
}
for (auto& it : p2) {
ans.push_back(it);
}
return ans;
}
if (find_edge(p1.back(), p2[0])) {
vector <int> ans;
for (auto& it : p1) {
ans.push_back(it);
}
for (auto& it : p2) {
ans.push_back(it);
}
return ans;
}
if (find_edge(p1.back(), p2.back())) {
vector <int> ans;
reverse(p2.begin(), p2.end());
for (auto& it : p1) {
ans.push_back(it);
}
for (auto& it : p2) {
ans.push_back(it);
}
return ans;
}
if (!are_connected(p1, p2)) {
if ((int)p1.size() > (int)p2.size()) {
return p1;
}
return p2;
}
int l = 0, r = (int)p1.size() - 1, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
vector <int> w;
for (int i = mid; i < (int)p1.size(); i++) {
w.push_back(p1[i]);
}
if (are_connected(w, p2)) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
int vert1 = ans;
l = 0; r = (int)p2.size() - 1; ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
vector <int> w;
for (int i = mid; i < (int)p2.size(); i++) {
w.push_back(p2[i]);
}
if (are_connected({ p1[vert1] }, w)) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
int vert2 = ans;
vector <int> final_ans;
for (int i = vert1 + 1; i < (int)p1.size(); i++) {
final_ans.push_back(p1[i]);
}
for (int i = 0; i <= vert1; i++) {
final_ans.push_back(p1[i]);
}
for (int i = vert2; i < (int)p2.size(); i++) {
final_ans.push_back(p2[i]);
}
for (int i = 0; i < vert2; i++) {
final_ans.push_back(p2[i]);
}
return final_ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
non-disjoint arrays |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 3 |
Halted |
0 ms |
0 KB |
- |
