#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
bool czy[300];
vector<int>polacz(vector<int>a, vector<int>b){
while(b.size()){
a.push_back(b.back());
b.pop_back();
}
return a;
}
vector<int>prefix(vector<int>A, int ile){
while((int)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(tab[0].size()==0)return tab[1];
if(tab[1].size()==0)return tab[0];
if(!are_connected(tab[0], tab[1])){
if(tab[0].size()>=tab[1].size())return tab[0];
return tab[1];
}
if(are_connected({tab[0].back()}, {tab[1].back()})){
tab[0] = polacz(tab[0], tab[1]);
tab[1].clear();
}
else if(are_connected({tab[0].back()}, {tab[1][0]})){
reverse(tab[1].begin(), tab[1].end());
tab[0] = polacz(tab[0], tab[1]);
tab[1].clear();
}
if(are_connected({tab[0][0]}, {tab[1].back()})){
reverse(tab[0].begin(), tab[0].end());
tab[0] = polacz(tab[0], tab[1]);
tab[1].clear();
}
if(are_connected({tab[0][0]}, {tab[1][1]})){
reverse(tab[0].begin(), tab[0].end());
reverse(tab[1].begin(), tab[1].end());
tab[0] = polacz(tab[0], tab[1]);
tab[1].clear();
}
if(tab[1].size()==0)return tab[0];
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<(int)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();
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<(int)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];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
non-disjoint arrays |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
596 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
