#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n,d;
vector<int>getslice(int l,int r,deque<int>&v){
vector<int>res;
for(int i=l;i<=r;i++){
res.pb(v[i]);
}
return res;
}
vector<int>longest_trip(int N,int D){
n=N,d=D;
deque<int>trip1,trip2;
trip1.pb(0);
for(int i=1;i<n;i++){
bool ok=are_connected({trip1.back()},{i});
if(ok){
trip1.pb(i);
}else if(trip1.size()==1){
trip2.pb(i);
}else{
ok=are_connected({trip1.front()},{i});
if(ok){
trip1.push_front(i);
}else{
trip2.pb(i);
}
}
}
if(!trip2.size())return vector<int>(trip1.begin(),trip1.end());
if(!are_connected(vector<int>(trip1.begin(),trip1.end()),vector<int>(trip2.begin(),trip2.end()))){
if(trip1.size()<trip2.size())swap(trip1,trip2);
return vector<int>(trip1.begin(),trip1.end());
}
if(are_connected({trip1.front()},{trip2.front()})){
vector<int>ans;
for(int i=trip1.size()-1;0<=i;i--){
ans.pb(trip1[i]);
}
for(int i:trip2){
ans.pb(i);
}
return ans;
}
if(are_connected({trip1.back()},{trip2.front()})){
vector<int>ans;
for(int i:trip1){
ans.pb(i);
}
for(int i:trip2){
ans.pb(i);
}
return ans;
}
int ans1=-1;
{
int l=0,r=trip1.size()-1;
while(l<=r){
int mid=(l+r)>>1;
bool ok=are_connected(getslice(l,mid,trip1),vector<int>(trip2.begin(),trip2.end()));
if(ok){
ans1=mid;
r=mid-1;
}else{
l=mid+1;
}
}
}
assert(ans1!=-1);
int ans2=-1;
{
int l=0,r=trip2.size()-1;
while(l<=r){
int mid=(l+r)>>1;
bool ok=are_connected(getslice(l,mid,trip2),{trip1[ans1]});
if(ok){
ans2=mid;
r=mid-1;
}else{
l=mid+1;
}
}
}
assert(ans2!=-1);
vector<int>ans;
for(int i=ans1+1;i<trip1.size();i++){
ans.pb(trip1[i]);
}
for(int i=0;i<=ans1;i++){
ans.pb(trip1[i]);
}
ans.pb(trip2[ans2]);
for(int i:trip2){
if(i!=trip2[ans2])ans.pb(i);
}
return ans;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i=ans1+1;i<trip1.size();i++){
| ~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
344 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 |
4 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
344 KB |
Output is correct |
5 |
Correct |
6 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 |
7 ms |
344 KB |
Output is correct |
6 |
Correct |
10 ms |
344 KB |
Output is correct |
7 |
Correct |
8 ms |
344 KB |
Output is correct |
8 |
Correct |
5 ms |
344 KB |
Output is correct |
9 |
Correct |
6 ms |
344 KB |
Output is correct |
10 |
Correct |
5 ms |
340 KB |
Output is correct |
11 |
Correct |
5 ms |
344 KB |
Output is correct |
12 |
Correct |
5 ms |
344 KB |
Output is correct |
13 |
Correct |
6 ms |
344 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 |
6 ms |
344 KB |
Output is correct |
5 |
Correct |
7 ms |
344 KB |
Output is correct |
6 |
Correct |
10 ms |
344 KB |
Output is correct |
7 |
Correct |
5 ms |
344 KB |
Output is correct |
8 |
Correct |
3 ms |
344 KB |
Output is correct |
9 |
Correct |
3 ms |
344 KB |
Output is correct |
10 |
Correct |
3 ms |
344 KB |
Output is correct |
11 |
Correct |
5 ms |
344 KB |
Output is correct |
12 |
Correct |
4 ms |
344 KB |
Output is correct |
13 |
Correct |
4 ms |
356 KB |
Output is correct |
14 |
Correct |
7 ms |
344 KB |
Output is correct |
15 |
Correct |
7 ms |
344 KB |
Output is correct |
16 |
Incorrect |
2 ms |
344 KB |
Incorrect |
17 |
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 |
5 ms |
344 KB |
Output is correct |
4 |
Correct |
4 ms |
344 KB |
Output is correct |
5 |
Correct |
5 ms |
344 KB |
Output is correct |
6 |
Correct |
7 ms |
344 KB |
Output is correct |
7 |
Correct |
6 ms |
344 KB |
Output is correct |
8 |
Correct |
5 ms |
344 KB |
Output is correct |
9 |
Correct |
5 ms |
344 KB |
Output is correct |
10 |
Correct |
6 ms |
344 KB |
Output is correct |
11 |
Correct |
5 ms |
344 KB |
Output is correct |
12 |
Correct |
5 ms |
344 KB |
Output is correct |
13 |
Correct |
5 ms |
344 KB |
Output is correct |
14 |
Correct |
7 ms |
344 KB |
Output is correct |
15 |
Correct |
10 ms |
344 KB |
Output is correct |
16 |
Incorrect |
2 ms |
344 KB |
Incorrect |
17 |
Halted |
0 ms |
0 KB |
- |