#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define ask are_connected
std::vector<int> longest_trip(int N, int D) {
int n = N;
vector <int> A = {0}, B;
for (int i = 1; i < n; i++) {
if (B.empty()) {
bool f = ask ({A.back()}, {i});
if (f)
A.push_back(i);
else {
B.push_back(i);
}
} else {
if (ask ({A.back()}, {B[0]})) {
for (int x : B)
A.push_back(x);
B.clear();
i--;
} else if (ask ({A.back()}, {i})) {
A.push_back(i);
} else {
B.push_back(i);
}
}
}/*
cout << "A : ";
for (int x : A)
cout << x << ' ';
cout << '\n';
cout << "B : ";
for (int y : B)
cout << y << ' ';
cout << '\n';*/
if (B.empty()) {
assert (A.size() == n);
return A;
}
if (!ask (A, B)) {
if (A.size() >= B.size()) {
assert (A.size() >= (n + 1) / 2);
return A;
}
assert (B.size() >= (n + 1) / 2);
return B;
}
if (ask ({A[0]}, {B[0]})) {
reverse (A.begin(), A.end());
for (int x : B) {
A.push_back(x);
}
assert (A.size() == n);
return A;
} else {
bool f;
if (A.size() >= 2) {
f = ask ({A[0]}, {A.back()});
if (!f) {
for (int x : B) {
A.push_back(x);
}
assert (A.size() == n);
return A;
}
}
if (B.size() >= 2) {
f = ask ({B[0]}, {B.back()});
if (!f) {
for (int x : A) {
B.push_back(x);
}
assert (B.size() == n);
return B;
}
}
}
int l = -1, r = (int)A.size() - 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
vector <int> C;
for (int i = 0; i <= mid; i++) {
C.push_back(A[i]);
}
if (ask (C, B)) {
r = mid;
} else {
l = mid;
}
}
vector <int> wef = {A[r]};
int ww1 = r;
l = -1, r = (int)B.size() - 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
vector <int> C;
for (int i = 0; i <= mid; i++) {
C.push_back(B[i]);
}
if (ask (C, wef)) {
r = mid;
} else {
l = mid;
}
}
int ww2 = r;
vector <int> ans;
for (int i = ww1 + 1; i < (int)A.size(); i++) {
ans.push_back(A[i]);
}
for (int i = 0; i <= ww1; i++) {
ans.push_back(A[i]);
}
for (int i = ww2; i < (int)B.size(); i++) {
ans.push_back(B[i]);
}
for (int i = 0; i < ww2; i++) {
ans.push_back(B[i]);
}
assert (ask ({A[ww1]}, {B[ww2]}));
assert (ask ({A[0]}, {A.back()}) || (int)A.size() == 1);
assert (ask ({B[0]}, {B.back()}) || (int)B.size() == 1);
assert (ans.size() == n);
for (int i = 0; i < n - 1; i++) {
// assert (ask ({ans[i]}, {ans[i + 1]}));
}
return ans;
}
Compilation message
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:2:
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:41:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | assert (A.size() == n);
| ~~~~~~~~~^~~~
longesttrip.cpp:46:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | assert (A.size() >= (n + 1) / 2);
| ~~~~~~~~~^~~~~~~~~~~~~~
longesttrip.cpp:49:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
49 | assert (B.size() >= (n + 1) / 2);
| ~~~~~~~~~^~~~~~~~~~~~~~
longesttrip.cpp:57:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
57 | assert (A.size() == n);
| ~~~~~~~~~^~~~
longesttrip.cpp:67:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
67 | assert (A.size() == n);
| ~~~~~~~~~^~~~
longesttrip.cpp:77:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
77 | assert (B.size() == n);
| ~~~~~~~~~^~~~
longesttrip.cpp:127:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
127 | assert (ans.size() == n);
| ~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
344 KB |
Output is correct |
| # |
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 |
5 ms |
420 KB |
Output is correct |
| 4 |
Correct |
7 ms |
344 KB |
Output is correct |
| 5 |
Correct |
6 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 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 |
7 ms |
344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
non-disjoint arrays |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 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 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Correct |
7 ms |
344 KB |
Output is correct |
| 3 |
Correct |
6 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
436 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
non-disjoint arrays |
| 7 |
Halted |
0 ms |
0 KB |
- |
