#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/egoi2024/d2/debug.h"
#else
#define debug(...) void(37)
#endif
vector<int> m(vector<int> x, vector<int> y) {
vector<int> res;
res = x;
res.insert(res.end(), y.begin(), y.end());
return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
std::vector<int> longest_trip(int N, int D) {
array<vector<int>, 2> l;
l[0] = {0}; l[1] = {1};
bool dis = false;
for (int i = 2; i < N; ++i) {
if (are_connected({i}, {l[0].back()})) {
dis = false;
l[0].push_back(i);
} else if (dis) {
l[1].push_back(i);
dis = false;
} else if (are_connected({i}, {l[1].back()})) {
l[1].push_back(i);
dis = true;
} else {
l[0] = m(l[0], vector<int>(l[1].rbegin(), l[1].rend()));
dis = int(l[1].size()) == 1;
l[1] = {i};
}
}
debug(l);
if (!are_connected(l[0], l[1])) {
return int(l[0].size()) > int(l[1].size()) ? l[0] : l[1];
}
vector<int> fe0, fe1;
int l0 = int(l[0].size());
int l1 = int(l[1].size());
for (int i = 0; i < l0; ++i) {
if (i == 0 || i == l0 - 1) fe0.push_back(l[0][i]);
}
for (int i = 0; i < l1; ++i) {
if (i == 0 || i == l1 - 1) fe1.push_back(l[1][i]);
}
if (!are_connected(fe0, fe1)) {
int s = -1;
{
int low = 0, high = int(l[1].size()) - 1;
while (low < high) {
int mid = (low + high) >> 1;
if (are_connected(l[0], vector<int>(l[1].begin(), l[1].begin() + mid + 1))) {
high = mid;
} else {
low = mid + 1;
}
}
s = low;
}
int f = -1;
{
int low = 0, high = int(l[0].size()) - 1;
while (low < high) {
int mid = (low + high) >> 1;
if (are_connected({l[1][s]}, vector<int>(l[0].begin(), l[0].begin() + mid + 1))) {
high = mid;
} else {
low = mid + 1;
}
}
f = low;
}
rotate(l[1].begin(), l[1].begin() + s, l[1].end());
if (f != int(l[0].size()) - 1) rotate(l[0].begin(), l[0].begin() + f + 1, l[0].end());
vector<int> ans = m(l[0], l[1]);
return ans;
}
vector<int> ans;
for (int it = 0; it < 2; ++it) {
for (int it1 = 0; it1 < 2; it1++) {
if (are_connected({l[0].back()}, {l[1][0]})) {
ans = m(l[0], l[1]);
}
reverse(l[1].begin(), l[1].end());
}
swap(l[0], l[1]);
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
344 KB |
Output is correct |
2 |
Correct |
7 ms |
344 KB |
Output is correct |
3 |
Correct |
4 ms |
344 KB |
Output is correct |
4 |
Correct |
5 ms |
344 KB |
Output is correct |
5 |
Correct |
6 ms |
600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
344 KB |
Output is correct |
2 |
Correct |
6 ms |
344 KB |
Output is correct |
3 |
Correct |
5 ms |
344 KB |
Output is correct |
4 |
Correct |
3 ms |
344 KB |
Output is correct |
5 |
Correct |
3 ms |
440 KB |
Output is correct |
6 |
Correct |
15 ms |
344 KB |
Output is correct |
7 |
Correct |
8 ms |
344 KB |
Output is correct |
8 |
Correct |
5 ms |
344 KB |
Output is correct |
9 |
Correct |
6 ms |
600 KB |
Output is correct |
10 |
Correct |
5 ms |
344 KB |
Output is correct |
11 |
Correct |
6 ms |
344 KB |
Output is correct |
12 |
Correct |
5 ms |
452 KB |
Output is correct |
13 |
Correct |
4 ms |
448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
344 KB |
Output is correct |
2 |
Correct |
9 ms |
344 KB |
Output is correct |
3 |
Correct |
7 ms |
344 KB |
Output is correct |
4 |
Correct |
5 ms |
436 KB |
Output is correct |
5 |
Correct |
6 ms |
344 KB |
Output is correct |
6 |
Correct |
14 ms |
344 KB |
Output is correct |
7 |
Correct |
12 ms |
344 KB |
Output is correct |
8 |
Correct |
9 ms |
344 KB |
Output is correct |
9 |
Correct |
5 ms |
444 KB |
Output is correct |
10 |
Correct |
3 ms |
600 KB |
Output is correct |
11 |
Correct |
6 ms |
344 KB |
Output is correct |
12 |
Correct |
5 ms |
344 KB |
Output is correct |
13 |
Correct |
4 ms |
344 KB |
Output is correct |
14 |
Correct |
5 ms |
344 KB |
Output is correct |
15 |
Correct |
6 ms |
344 KB |
Output is correct |
16 |
Incorrect |
6 ms |
344 KB |
Incorrect |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
344 KB |
Output is correct |
3 |
Correct |
7 ms |
344 KB |
Output is correct |
4 |
Correct |
6 ms |
344 KB |
Output is correct |
5 |
Correct |
5 ms |
344 KB |
Output is correct |
6 |
Correct |
14 ms |
344 KB |
Output is correct |
7 |
Correct |
8 ms |
344 KB |
Output is correct |
8 |
Correct |
7 ms |
344 KB |
Output is correct |
9 |
Correct |
7 ms |
344 KB |
Output is correct |
10 |
Correct |
6 ms |
600 KB |
Output is correct |
11 |
Correct |
4 ms |
448 KB |
Output is correct |
12 |
Correct |
6 ms |
344 KB |
Output is correct |
13 |
Correct |
4 ms |
340 KB |
Output is correct |
14 |
Correct |
7 ms |
344 KB |
Output is correct |
15 |
Correct |
10 ms |
344 KB |
Output is correct |
16 |
Incorrect |
6 ms |
344 KB |
Incorrect |
17 |
Halted |
0 ms |
0 KB |
- |