#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> longest_trip(int N, int D){
#define pb push_back
vector <int> v1,v2;
v1.pb(0);
for (int i=1; i<N; i++){
if (v2.empty()){
if (are_connected({i},{v1.front()})){
v1.insert(v1.begin(),i);
} else {
v2.pb(i);
}
continue;
}
if (i+1==N){
bool a=are_connected({i},{v1.front()});
bool b=are_connected({i},{v2.front()});
if (a&&b){
v2.insert(v2.begin(),i);
for (int j:v2) v1.insert(v1.begin(),j);
v2.clear();
} else if (a){
v1.insert(v1.begin(),i);
} else if (b){
v2.insert(v2.begin(),i);
}
} else {
if (are_connected({i},{i+1})){
if (are_connected({i},{v1.front()})){
v1.insert(v1.begin(),i);
v1.insert(v1.begin(),i+1);
} else {
v2.insert(v2.begin(),i);
v2.insert(v2.begin(),i+1);
}
if (are_connected({v1.front()},{v2.front()})){
for (auto i:v2) v1.insert(v1.begin(),i);
v2.clear();
}
} else {
if (are_connected({i},{v1.front()})){
v1.insert(v1.begin(),i);
v2.insert(v2.begin(),i+1);
} else {
v2.insert(v2.begin(),i);
v1.insert(v1.begin(),i+1);
}
}
}
}
if (v2.empty()) return v1;
if (!are_connected(v1,v2)){
if (v1.size()>=v2.size()) return v1;
return v2;
}
if (are_connected({v1.front()},{v2.back()})){
for (int i:v1) v2.pb(i);
return v2;
}
if (are_connected({v1.front()},{v2.front()})){
for (int i:v2) v2.insert(v2.begin(),i);
return v2;
}
if (are_connected({v2.front()},{v1.back()})){
for (int i:v2) v1.pb(i);
return v1;
}
vector <int> c1=v1;
while (c1.size()>1){
int tp=c1.size()/2;
vector <int> tp1,tp2;
for (int i=0; i<c1.size(); i++){
if (i<tp) tp1.pb(c1[i]);
else tp2.pb(c1[i]);
}
if (are_connected(tp1,v2)) c1=tp1;
else c1=tp2;
}
vector <int> c2=v2;
while (c2.size()>1){
int tp=c2.size()/2;
vector <int> tp1,tp2;
for (int i=0; i<c2.size(); i++){
if (i<tp) tp1.pb(c2[i]);
else tp2.pb(c2[i]);
}
if (are_connected(c1,tp1)) c2=tp1;
else c2=tp2;
}
vector <int> ret;
int pos=0;
for (int i=0; i<v1.size(); i++){
if (v1[i]==c1[0]) pos=i;
}
for (int i=(pos+1)%v1.size(),cnt=0; cnt<v1.size(); i=(i+1)%v1.size(),cnt++){
ret.pb(v1[i]);
}
pos=0;
for (int i=0; i<v2.size(); i++){
if (v2[i]==c2[0]) pos=i;
}
for (int i=pos,cnt=0; cnt<v2.size(); i=(i+1)%v2.size(),cnt++){
ret.pb(v2[i]);
}
return ret;
#undef pb
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:74:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i=0; i<c1.size(); i++){
| ~^~~~~~~~~~
longesttrip.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i=0; i<c2.size(); i++){
| ~^~~~~~~~~~
longesttrip.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i=0; i<v1.size(); i++){
| ~^~~~~~~~~~
longesttrip.cpp:97:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int i=(pos+1)%v1.size(),cnt=0; cnt<v1.size(); i=(i+1)%v1.size(),cnt++){
| ~~~^~~~~~~~~~
longesttrip.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int i=0; i<v2.size(); i++){
| ~^~~~~~~~~~
longesttrip.cpp:104:30: 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=pos,cnt=0; cnt<v2.size(); i=(i+1)%v2.size(),cnt++){
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
4 ms |
600 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 |
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 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 8 |
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 |
416 KB |
Output is correct |
| 5 |
Correct |
5 ms |
344 KB |
Output is correct |
| 6 |
Correct |
7 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 8 |
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 |
600 KB |
Output is correct |
| 6 |
Correct |
7 ms |
352 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 8 |
Halted |
0 ms |
0 KB |
- |
