#include "longesttrip.h"
#include <algorithm>
#include <random>
#include <stack>
using namespace std;
vector<int> longest_trip(int N, int D)
{
vector<int> big, small, nodes;
for (int i = 0; i < N; i++)
nodes.push_back(i);
random_device rd;
mt19937 g(rd());
shuffle(nodes.begin(), nodes.end(), g);
big.push_back(nodes[0]);
small.push_back(nodes[1]);
bool guarantee = false;
for (int i = 2; i < N; i++) {
if (are_connected(vector<int>{big.back()}, vector<int>{i})) {
big.push_back(nodes[i]);
guarantee = false;
} else if (guarantee) {
small.push_back(nodes[i]);
} else if (are_connected(vector<int>{small.back()}, vector<int>{i})) {
small.push_back(nodes[i]);
guarantee = true;
} else {
if (small.size() == 1) guarantee = true;
while (!small.empty()) {
big.push_back(small.back());
small.pop_back();
}
small.push_back(nodes[i]);
}
}
if (are_connected(big, small)) {
if (are_connected(vector<int>{big.back()}, vector<int>{small.back()}) ||
are_connected(vector<int>{big[0]}, vector<int>{small[0]}) ) {
big.insert(big.end(), small.rbegin(), small.rend());
return big;
}
if (are_connected(vector<int>{big.back()}, vector<int>{small[0]}) ||
are_connected(vector<int>{big[0]}, vector<int>{small.back()})) {
big.insert(big.end(), small.begin(), small.end());
return big;
}
int l = 0, r = big.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
std::vector<int>::iterator begin = big.begin() + l; // Start from index 1
std::vector<int>::iterator end = big.begin() + mid + 1;
vector<int> tempBig(begin, end);
if (are_connected(small, tempBig)) {
r = mid;
} else {
l = mid + 1;
}
}
int bigInd = l;
l = 0, r = small.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
std::vector<int>::iterator begin = small.begin() + l; // Start from index 1
std::vector<int>::iterator end = small.begin() + mid + 1;
vector<int> tempSmall(begin, end);
if (are_connected(tempSmall, vector<int>{big[bigInd]})) {
r = mid;
} else {
l = mid + 1;
}
}
int smallInd = l;
vector<int> ans;
for (int i = smallInd + 1; i < small.size(); i++) {
ans.push_back(small[i]);
}
for (int i = 0; i <= smallInd; i++) {
ans.push_back(small[i]);
}
for (int i = bigInd; i <= big.size(); i++) {
ans.push_back(big[i]);
}
for (int i = 0; i < bigInd; i++) {
ans.push_back(big[i]);
}
return ans;
} else {
if (big.size() < small.size()) return small;
else return big;
}
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:84:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = smallInd + 1; i < small.size(); i++) {
| ~~^~~~~~~~~~~~~~
longesttrip.cpp:90:32: 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 = bigInd; i <= big.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
544 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
