#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
#define vi vector<int>
const int N = 200005;
std::vector<int> longest_trip(int n, int D)
{
if(D == 3){
vector<int> v;
for(int i = 0; i < n; ++i) v.pb(i);
return v;
}
if(D == 2){
deque<int> v;
v.pb(0);
int o = -1;
for(int i = 1; i < n; ++i){
bool x = are_connected(vi{0}, vi{i});
if(x){
o = i;
v.pb(i);
break;
}
}
if(o == -1){
vi res;
for(int i = 1; i < n; ++i){
res.pb(i);
}
return res;
}
for(int i = 1; i < n; ++i){
if(o == i) continue;
bool x = are_connected(vi{v[0]}, vi{i});
if(x){
v.push_front(i);
}else v.pb(i);
}
vector<int> res(all(v));
return res;
}
vector<vector<int>> g(n);
deque<int> a, b;
a.pb(0);
for(int i = 1; i < n; ++i){
if(are_connected(vi{a.back()}, vi{i})){
a.pb(i);
}else if(!b.empty() && are_connected(vi{b.back()}, vi{i})){
b.pb(i);
}else{
if(b.empty()) b.pb(i);
else{
reverse(all(b));
for(int x: b) a.pb(x);
b.clear();
b.pb(i);
}
}
// for(int x:)
}
if(b.size()>a.size())swap(a,b);
vi A(all(a));
vi B(all(b));
if(B.empty()) return A;
if(are_connected(A, B) == 0){
// for(int i = 0 ; i + 1 < A.size(); ++i) assert(are_connected(vi{A[i]}, vi{A[i+1]}));
return A;
}
int u = -1, v;
if(are_connected(vi{a[0]}, vi{a.back()}) == 0){
if(are_connected(vi{a[0]}, vi{b.back()}) == 1){
reverse(all(b));
for(int x: b) a.push_front(x);
}else{
reverse(all(b));
for(int x: b) a.pb(x);
}
}else if(are_connected(vi{b[0]}, vi{b.back()}) == 0){
if(are_connected(vi{a[0]}, vi{b.back()}) == 1){
reverse(all(b));
for(int x: b) a.push_front(x);
}else{
reverse(all(b));
for(int x: b) a.pb(x);
}else{
// cout << "f" << endl;
int ul = 0, ur = int(b.size()) - 1, ub = -1; vi aa(all(a));
while(ul <= ur){
int um = ul+ur>>1;
vi z;
for(int j = 0; j <= um; ++j) z.pb(b[j]);
if(are_connected(z, aa)){
ub = um;
ur = um - 1;
}else ul = um + 1;
}
if(ub == -1){
assert(false);
return aa;
}
ul = 0, ur = int(a.size()) - 1; int ua = -1;
while(ul <= ur){
int um = ul+ur>>1;
vi z;
for(int j = 0; j <= um; ++j) z.pb(a[j]);
if(are_connected(z, vi{b[ub]})){
ua = um;
ur = um - 1;
}else ul = um + 1;
}
if(ua == -1){
assert(false);
vi res(all(a));
return res;
}
int uu = b[ub];
while(b.front() != uu){
int x = b.front();
b.pop_front();
b.pb(x);
}
u = a[ua];
while(a.front() != u){
int x = a.front();
a.pop_front();
a.pb(x);
}
// for(int i = 0 ; i + 1 < b.size(); ++i) assert(are_connected(vi{b[i]}, vi{b[i+1]}));
// for(int i = 0 ; i + 1 < a.size(); ++i) assert(are_connected(vi{a[i]}, vi{a[i+1]}));
// assert(are_connected(vi{u}, vi{uu}));
for(int x: b) a.push_front(x);
// for(int i = 0 ; i + 1 < a.size(); ++i) assert(are_connected(vi{a[i]}, vi{a[i+1]}));
}
vi res(all(a));
return res;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:97:4: error: expected '}' before 'else'
97 | }else{
| ^~~~
longesttrip.cpp:90:55: note: to match this '{'
90 | }else if(are_connected(vi{b[0]}, vi{b.back()}) == 0){
| ^
longesttrip.cpp:101:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
101 | int um = ul+ur>>1;
| ~~^~~
longesttrip.cpp:115:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
115 | int um = ul+ur>>1;
| ~~^~~
longesttrip.cpp:81:15: warning: unused variable 'v' [-Wunused-variable]
81 | int u = -1, v;
| ^
