#include "longesttrip.h"
// 123
#include <bits/stdc++.h>
using namespace std;
std::vector<int> longest_trip(int N, int D) {
vector<int> a[2];
a[0] = {0};
int i = 1;
for (; i < N; i++) {
if (are_connected({a[0].back()}, {i})) {
a[0].emplace_back(i);
} else {
a[1].emplace_back(i++);
break;
}
}
bool merge = 0;
bool ask = 0;
int last_merge_pos = -1;
for (; i < N; i++) {
int x = a[0].back();
int y = a[1].back();
if (merge) {
assert(a[1].back() == i - 1);
if (are_connected({i - 1}, {i})) {
a[1].emplace_back(i);
} else {
a[0].insert(a[0].begin() + last_merge_pos, i);
}
merge = 0;
} else if (are_connected({i}, {x})) {
a[0].emplace_back(i);
} else {
if (ask) {
a[1].emplace_back(i);
ask = 0;
} else {
if (are_connected({i}, {y})) {
a[1].emplace_back(i);
ask = 1;
} else {
last_merge_pos = a[0].size();
merge = 1;
while (a[1].size()) a[0].emplace_back(a[1].back()), a[1].pop_back();
a[1].emplace_back(i);
}
}
}
}
if (a[0].size() == N) return a[0];
assert(a[0].size() + a[1].size() == N);
int x = a[0][0], y = a[0].back();
int z = a[1][0], t = a[1].back();
auto join = [&](int p, int q) {
if (p) reverse(a[0].begin(), a[0].end());
if (q) reverse(a[1].begin(), a[1].end());
a[0].insert(a[0].end(), a[1].begin(), a[1].end());
return a[0];
};
if (are_connected({x}, {z})) {
return join(1, 0);
} else if (are_connected({x}, {t})) {
return join(1, 1);
} else if (are_connected({y}, {z})) {
return join(0, 0);
} else if (are_connected({y}, {t})) {
return join(0, 1);
} else {
int l1 = 0, r1 = a[0].size();
int l2 = 0, r2 = a[1].size();
auto ask = [&](int x, int y, int z, int t) {
vector<int> p, q;
for (int i = x; i < y; i++) p.emplace_back(a[0][i]);
for (int i = z; i < t; i++) q.emplace_back(a[1][i]);
if (p.size() && q.size()) return are_connected(p, q);
return false;
};
if (!ask(l1, r1, l2, r2)) {
if (a[0].size() < a[1].size()) swap(a[0], a[1]);
return a[0];
} else {
while (l1 + 1 < r1) {
int m = l1 + r1 >> 1;
if (ask(l1, m, l2, r2)) {
r1 = m;
} else {
l1 = m;
}
}
while (l2 + 1 < r2) {
int m = l2 + r2 >> 1;
if (ask(l1, r1, l2, m)) {
r2 = m;
} else {
l2 = m;
}
}
assert(l1 + 1 == r1 && l2 + 1 == r2);
vector<int> ans;
for (int i = r1; i < a[0].size(); i++) ans.emplace_back(a[0][i]);
for (int i = 0; i < r1; i++) ans.emplace_back(a[0][i]);
for (int i = l2; i < a[1].size(); i++) ans.emplace_back(a[1][i]);
for (int i = 0; i < l2; i++) ans.emplace_back(a[1][i]);
return ans;
}
}
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:52:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
52 | if (a[0].size() == N) return a[0];
| ~~~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from longesttrip.cpp:4:
longesttrip.cpp:53:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
53 | assert(a[0].size() + a[1].size() == N);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
longesttrip.cpp:85:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int m = l1 + r1 >> 1;
| ~~~^~~~
longesttrip.cpp:93:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
93 | int m = l2 + r2 >> 1;
| ~~~^~~~
longesttrip.cpp:102:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int i = r1; i < a[0].size(); i++) ans.emplace_back(a[0][i]);
| ~~^~~~~~~~~~~~~
longesttrip.cpp:104:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int i = l2; i < a[1].size(); i++) ans.emplace_back(a[1][i]);
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
344 KB |
Output is correct |
| 3 |
Correct |
4 ms |
344 KB |
Output is correct |
| 4 |
Correct |
4 ms |
344 KB |
Output is correct |
| 5 |
Correct |
4 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Correct |
4 ms |
344 KB |
Output is correct |
| 3 |
Correct |
4 ms |
344 KB |
Output is correct |
| 4 |
Correct |
4 ms |
344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
600 KB |
Output is correct |
| 6 |
Correct |
6 ms |
344 KB |
Output is correct |
| 7 |
Correct |
5 ms |
344 KB |
Output is correct |
| 8 |
Correct |
5 ms |
344 KB |
Output is correct |
| 9 |
Correct |
4 ms |
344 KB |
Output is correct |
| 10 |
Correct |
4 ms |
344 KB |
Output is correct |
| 11 |
Correct |
4 ms |
344 KB |
Output is correct |
| 12 |
Correct |
5 ms |
344 KB |
Output is correct |
| 13 |
Correct |
4 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Correct |
6 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 |
4 ms |
344 KB |
Output is correct |
| 6 |
Correct |
8 ms |
344 KB |
Output is correct |
| 7 |
Correct |
5 ms |
344 KB |
Output is correct |
| 8 |
Correct |
4 ms |
344 KB |
Output is correct |
| 9 |
Correct |
4 ms |
344 KB |
Output is correct |
| 10 |
Correct |
5 ms |
344 KB |
Output is correct |
| 11 |
Correct |
5 ms |
600 KB |
Output is correct |
| 12 |
Correct |
4 ms |
344 KB |
Output is correct |
| 13 |
Correct |
5 ms |
344 KB |
Output is correct |
| 14 |
Correct |
14 ms |
344 KB |
Output is correct |
| 15 |
Incorrect |
5 ms |
344 KB |
Incorrect |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
596 KB |
Output is correct |
| 2 |
Correct |
5 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 |
4 ms |
344 KB |
Output is correct |
| 6 |
Correct |
7 ms |
344 KB |
Output is correct |
| 7 |
Correct |
5 ms |
344 KB |
Output is correct |
| 8 |
Correct |
4 ms |
344 KB |
Output is correct |
| 9 |
Correct |
5 ms |
344 KB |
Output is correct |
| 10 |
Correct |
4 ms |
496 KB |
Output is correct |
| 11 |
Correct |
5 ms |
540 KB |
Output is correct |
| 12 |
Correct |
4 ms |
344 KB |
Output is correct |
| 13 |
Correct |
4 ms |
344 KB |
Output is correct |
| 14 |
Correct |
15 ms |
344 KB |
Output is correct |
| 15 |
Incorrect |
7 ms |
344 KB |
Incorrect |
| 16 |
Halted |
0 ms |
0 KB |
- |
