#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
deque<deque<int>> combine(deque<deque<int>> p, int a, int b) {
deque<deque<int>> erg;
for (int i = 0; i < p.size(); i++)
if (i != a && i != b) erg.push_back(p[i]);
for (int i: p[a]) p[b].push_front(i);
erg.push_back(p[b]);
return erg;
}
vector<int> v(deque<int> d) {
vector<int> erg;
for (int i: d)
erg.push_back(i);
return erg;
}
int search(deque<int> a, deque<int> b) {
deque<int> l, r;
while (a.size() > 1) {
for (int i = 0; i < a.size(); i++)
{
(i % 2 ? l : r).push_back(a[i]);
}
a = are_connected(v(l), v(b)) ? l : r;
l.clear(); r.clear();
}
return a[0];
}
void push(vector<int> & v, deque<int> d, int ind) {
for (int i = 0; i < d.size(); i++)
{
v.push_back(d[(ind + i) % d.size()]);
}
}
int find(deque<int> d, int v) {
for (int i = 0; i < d.size(); i++)
if (d[i] == v) return i;
}
vector<int> longest_trip(int N, int D)
{
deque<int> unused;
for (int i = 0; i < N; i++)
unused.push_back(i);
deque<deque<int>> paths;
while (unused.size() >= 4) {
random_shuffle(unused.begin(), unused.end());
if (are_connected({unused[0]}, {unused[1]})) {
paths.push_back({unused[0], unused[1]});
for (int i = 0; i < 2; i++)
unused.pop_front();
} else {
deque<int> p0{unused[0]}, p1{unused[1]};
(are_connected({unused[0]}, {unused[2]}) ? p0 : p1).push_back(unused[2]);
(are_connected({unused[0]}, {unused[3]}) ? p0 : p1).push_back(unused[3]);
int u = -1;
if (p0.size() == 1) u = unused[0]; else paths.push_back(p0);
if (p1.size() == 1) u = unused[1]; else paths.push_back(p1);
for (int i = 0; i < 4; i++)
unused.pop_front();
if (u != -1) unused.push_front(u);
}
}
for (int i: unused) paths.push_back({i});
while (paths.size() > 2) {
random_shuffle(paths.begin(), paths.end());
if (are_connected({paths[0].front()}, {paths[1].front()})) {
paths = combine(paths, 0, 1);
} else if (are_connected({paths[0].front()}, {paths[2].front()})) {
paths = combine(paths, 0, 2);
} else {
paths = combine(paths, 1, 2);
}
}
if (are_connected(v(paths[0]), v(paths[1]))) {
if (are_connected({paths[0].front()}, {paths[1].front()})) {
return v(combine({paths[0], paths[1]}, 0, 1)[0]);
}
if (are_connected({paths[0].front()}, {paths[1].back()})) {
reverse(paths[1].begin(), paths[1].end());
return v(combine({paths[0], paths[1]}, 0, 1)[0]);
}
if (are_connected({paths[0].back()}, {paths[1].front()})) {
reverse(paths[0].begin(), paths[0].end());
return v(combine({paths[0], paths[1]}, 0, 1)[0]);
}
int c0 = find(paths[0], search(paths[0], paths[1]));
int c1 = find(paths[1], search(paths[1], {paths[0][c0]}));
vector<int> erg;
push(erg, paths[0], c0 + 1);
push(erg, paths[1], c1);
return erg;
} else {
return v(paths[0].size() > paths[1].size() ? paths[0] : paths[1]);
}
}
Compilation message
longesttrip.cpp: In function 'std::deque<std::deque<int> > combine(std::deque<std::deque<int> >, int, int)':
longesttrip.cpp:8:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | for (int i = 0; i < p.size(); i++)
| ~~^~~~~~~~~~
longesttrip.cpp: In function 'int search(std::deque<int>, std::deque<int>)':
longesttrip.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
longesttrip.cpp: In function 'void push(std::vector<int>&, std::deque<int>, int)':
longesttrip.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0; i < d.size(); i++)
| ~~^~~~~~~~~~
longesttrip.cpp: In function 'int find(std::deque<int>, int)':
longesttrip.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 0; i < d.size(); i++)
| ~~^~~~~~~~~~
longesttrip.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
45 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
4 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
344 KB |
Output is correct |
| 2 |
Correct |
6 ms |
344 KB |
Output is correct |
| 3 |
Correct |
8 ms |
344 KB |
Output is correct |
| 4 |
Correct |
9 ms |
344 KB |
Output is correct |
| 5 |
Correct |
13 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
344 KB |
Output is correct |
| 2 |
Correct |
7 ms |
344 KB |
Output is correct |
| 3 |
Correct |
7 ms |
344 KB |
Output is correct |
| 4 |
Correct |
14 ms |
344 KB |
Output is correct |
| 5 |
Correct |
15 ms |
852 KB |
Output is correct |
| 6 |
Correct |
13 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Incorrect |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
344 KB |
Output is correct |
| 2 |
Correct |
9 ms |
344 KB |
Output is correct |
| 3 |
Correct |
8 ms |
344 KB |
Output is correct |
| 4 |
Correct |
11 ms |
344 KB |
Output is correct |
| 5 |
Correct |
18 ms |
600 KB |
Output is correct |
| 6 |
Correct |
9 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Incorrect |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
344 KB |
Output is correct |
| 2 |
Correct |
8 ms |
448 KB |
Output is correct |
| 3 |
Correct |
8 ms |
344 KB |
Output is correct |
| 4 |
Correct |
9 ms |
344 KB |
Output is correct |
| 5 |
Correct |
13 ms |
600 KB |
Output is correct |
| 6 |
Correct |
9 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Incorrect |
| 8 |
Halted |
0 ms |
0 KB |
- |
