#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N, int D) {
vector<int> trip1(1, 0), trip2;
for (int i = 1; i < N; i++) {
bool b = are_connected(vector<int>(1, trip1.front()), vector<int>(1, i)),
b2 = are_connected(vector<int>(1, trip1.back()), vector<int>(1, i));
if (!b && !b2)
trip2.push_back(i);
else if (trip2.empty()) {
if (b)
trip1.insert(trip1.begin(), i);
else
trip2.push_back(i);
} else if (b) {
bool b3 = are_connected(vector<int>(1, trip2.front()), vector<int>(1, i)),
b4 = are_connected(vector<int>(1, trip2.back()), vector<int>(1, i));
if (b3) {
trip1.insert(trip1.begin(), i);
for (auto a : trip2) trip1.insert(trip1.begin(), a);
trip2.clear();
} else if (b4) {
trip2.push_back(i);
for (auto a : trip1) trip2.push_back(a);
trip1 = trip2;
trip2.clear();
} else {
trip1.insert(trip1.begin(), i);
}
} else if (b2) {
bool b3 = are_connected(vector<int>(1, trip2.front()), vector<int>(1, i)),
b4 = are_connected(vector<int>(1, trip2.back()), vector<int>(1, i));
if (b3) {
trip1.push_back(i);
for (auto a : trip2) trip1.push_back(a);
trip2.clear();
} else if (b4) {
reverse(trip2.begin(), trip2.end());
trip1.push_back(i);
for (auto a : trip2) trip1.push_back(a);
trip2.clear();
} else {
trip1.push_back(i);
}
}
}
if (trip2.empty()) return trip1;
if (are_connected(trip1, trip2)) {
if (trip1.size() != 1) {
if (!are_connected(vector<int>(1, trip1.front()),
vector<int>(1, trip1.back())))
while (1) {
}
}
if (trip2.size() != 1) {
if (!are_connected(vector<int>(1, trip2.front()),
vector<int>(1, trip2.back())))
while (1) {
}
}
int l = 0, r = int(trip1.size()) - 1;
while (l < r) {
int mid = (l + r) / 2;
vector<int> tmp;
for (int i = l; i <= mid; i++) tmp.push_back(trip1[i]);
if (are_connected(tmp, trip2))
r = mid;
else
l = mid + 1;
}
int firstone = l;
l = 0, r = int(trip2.size()) - 1;
while (l < r) {
int mid = (l + r) / 2;
vector<int> tmp;
for (int i = l; i <= mid; i++) tmp.push_back(trip2[i]);
if (are_connected(tmp, vector<int>(1, trip1[firstone])))
r = mid;
else
l = mid + 1;
}
int secondone = l;
vector<int> ans;
for (int i = firstone + 1; i < trip1.size(); i++) ans.push_back(trip1[i]);
for (int i = 0; i <= firstone; i++) ans.push_back(trip1[i]);
for (int i = secondone; i < trip2.size(); i++) ans.push_back(trip2[i]);
for (int i = 0; i < secondone; i++) ans.push_back(trip2[i]);
return ans;
}
if (trip1.size() < trip2.size()) trip1.swap(trip2);
return trip1;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:88:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = firstone + 1; i < trip1.size(); i++) ans.push_back(trip1[i]);
| ~~^~~~~~~~~~~~~~
longesttrip.cpp:90:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = secondone; i < trip2.size(); i++) ans.push_back(trip2[i]);
| ~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
3 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
344 KB |
Output is correct |
2 |
Correct |
13 ms |
344 KB |
Output is correct |
3 |
Correct |
14 ms |
512 KB |
Output is correct |
4 |
Correct |
13 ms |
344 KB |
Output is correct |
5 |
Correct |
15 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
344 KB |
Output is correct |
2 |
Correct |
10 ms |
344 KB |
Output is correct |
3 |
Correct |
9 ms |
344 KB |
Output is correct |
4 |
Correct |
12 ms |
344 KB |
Output is correct |
5 |
Correct |
8 ms |
344 KB |
Output is correct |
6 |
Correct |
15 ms |
344 KB |
Output is correct |
7 |
Correct |
17 ms |
344 KB |
Output is correct |
8 |
Correct |
12 ms |
344 KB |
Output is correct |
9 |
Correct |
14 ms |
596 KB |
Output is correct |
10 |
Correct |
12 ms |
344 KB |
Output is correct |
11 |
Correct |
10 ms |
596 KB |
Output is correct |
12 |
Correct |
13 ms |
600 KB |
Output is correct |
13 |
Correct |
10 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
344 KB |
Output is correct |
2 |
Correct |
10 ms |
344 KB |
Output is correct |
3 |
Correct |
13 ms |
344 KB |
Output is correct |
4 |
Correct |
9 ms |
344 KB |
Output is correct |
5 |
Correct |
10 ms |
344 KB |
Output is correct |
6 |
Correct |
11 ms |
344 KB |
Output is correct |
7 |
Correct |
10 ms |
344 KB |
Output is correct |
8 |
Correct |
14 ms |
344 KB |
Output is correct |
9 |
Correct |
10 ms |
344 KB |
Output is correct |
10 |
Correct |
14 ms |
344 KB |
Output is correct |
11 |
Correct |
16 ms |
340 KB |
Output is correct |
12 |
Correct |
12 ms |
436 KB |
Output is correct |
13 |
Correct |
9 ms |
344 KB |
Output is correct |
14 |
Correct |
16 ms |
344 KB |
Output is correct |
15 |
Correct |
12 ms |
344 KB |
Output is correct |
16 |
Execution timed out |
3046 ms |
344 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
344 KB |
Output is correct |
2 |
Correct |
12 ms |
344 KB |
Output is correct |
3 |
Correct |
9 ms |
344 KB |
Output is correct |
4 |
Correct |
14 ms |
344 KB |
Output is correct |
5 |
Partially correct |
11 ms |
600 KB |
Output is partially correct |
6 |
Correct |
11 ms |
344 KB |
Output is correct |
7 |
Correct |
12 ms |
344 KB |
Output is correct |
8 |
Correct |
10 ms |
344 KB |
Output is correct |
9 |
Correct |
12 ms |
504 KB |
Output is correct |
10 |
Partially correct |
10 ms |
344 KB |
Output is partially correct |
11 |
Partially correct |
14 ms |
344 KB |
Output is partially correct |
12 |
Partially correct |
12 ms |
344 KB |
Output is partially correct |
13 |
Partially correct |
16 ms |
600 KB |
Output is partially correct |
14 |
Correct |
16 ms |
344 KB |
Output is correct |
15 |
Correct |
11 ms |
340 KB |
Output is correct |
16 |
Execution timed out |
3069 ms |
344 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |