#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
bool czy[300];
vector<int>prefix(vector<int>A, int ile){
while(A.size()>ile)A.pop_back();
return A;
}
vector<int> longest_trip(int n, int d)
{
int i;
vector<int>tab[2];tab[0].push_back(0);tab[1].push_back(1);
for(i=1;i<n/2;i++){
int a = i*2, b = i*2+1;
if(are_connected({a}, {b})){
if(are_connected({a}, {tab[0].back()})){
tab[0].push_back(a);
tab[0].push_back(b);
}
else if(are_connected({a}, {tab[1].back()})){
tab[1].push_back(a);
tab[1].push_back(b);
}
else{
while(tab[1].size()){
tab[0].push_back(tab[1].back());
tab[1].pop_back();
}
tab[1].push_back(a);
tab[1].push_back(b);
}
}
else{
if(are_connected({a}, {tab[0].back()})){
tab[0].push_back(a);
if(are_connected({b}, {tab[1].back()}))
tab[1].push_back({b});
else{
while(tab[1].size()){
tab[0].push_back(tab[1].back());
tab[1].pop_back();
}
tab[1].push_back(b);
}
}
else{
tab[0].push_back(b);
if(are_connected({a}, {tab[1].back()}))
tab[1].push_back({a});
else{
while(tab[1].size()){
tab[0].push_back(tab[1].back());
tab[1].pop_back();
}
tab[1].push_back(a);
}
}
}
}
if(n%2){
if(are_connected({n-1}, {tab[0].back()}))
tab[0].push_back(n-1);
else if(are_connected({n-1}, {tab[1].back()}))
tab[1].push_back(n-1);
else{
while(tab[1].size()){
tab[0].push_back(tab[1].back());
tab[1].pop_back();
}
tab[1].push_back(n-1);
}
}
if(!are_connected(tab[0], tab[1])){
if(tab[0].size()>=tab[1].size())return tab[0];
return tab[1];
}
int pocz=0, kon = tab[0].size(), srodek;
while(pocz<kon){
srodek = (pocz+kon)/2;
if(are_connected(prefix(tab[0], srodek), tab[1]))
kon = srodek;
else
pocz = srodek+1;
}
vector<int>pom;
for(i=kon;i<tab[0].size();i++)
pom.push_back(tab[0][i]);
for(i=0;i<kon;i++)
pom.push_back(tab[0][i]);
tab[0] = pom;
pocz=0, kon = tab[1].size(), srodek;
while(pocz<kon){
srodek = (pocz+kon)/2;
if(are_connected(prefix(tab[1], srodek), tab[0]))
kon = srodek;
else
pocz = srodek+1;
}
pom.clear();
for(i=kon;i<tab[1].size();i++)
pom.push_back(tab[1][i]);
for(i=0;i<kon;i++)
pom.push_back(tab[1][i]);
tab[1] = pom;
while(tab[1].size()){
tab[0].push_back(tab[1].back());
tab[1].pop_back();
}
return tab[0];
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> prefix(std::vector<int>, int)':
longesttrip.cpp:6:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
6 | while(A.size()>ile)A.pop_back();
| ~~~~~~~~^~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:87:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(i=kon;i<tab[0].size();i++)
| ~^~~~~~~~~~~~~~
longesttrip.cpp:93:37: warning: right operand of comma operator has no effect [-Wunused-value]
93 | pocz=0, kon = tab[1].size(), srodek;
| ^
longesttrip.cpp:102:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(i=kon;i<tab[1].size();i++)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
