#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(15645869);
std::vector<int> longest_trip(int N, int D)
{
vector<int>x, y;
vector<int>p;
for(int i=0;i<N;i++){
p.push_back(i);
}
set<pair<int,int>>yes;
set<pair<int,int>>no;
auto conn = [&](vector<int>x,vector<int>y) bool {
int c1=0;
for(int a: x){
for(int b: y){
if(yes.count({a,b})){
return true;
}
c1 += no.count({a,b});
}
}
if(c1==x.size()*y.size()){
return false;
}
bool ans = are_connected(x,y);
if(!ans){
for(int a: x){
for(int b: y){
no.insert({a,b});
for(int c=0;c<N;c++){
if(no.count({a,c}) && c!=a && c!=b){
yes.insert({b,c});
yes.insert({c,b});
}
if(no.count({b,c}) && c!=a && c!=b){
yes.insert({a,c});
yes.insert({c,a});
}
}
}
}
}
if(ans && x.size()==1 && y.size()==1){
yes.insert({x[0], y[0]});
yes.insert({y[0], x[0]});
}
return ans;
};
auto fix=[&](){
if(x.size()==0 || y.size()==0){
return;
}
for(int a: x){
for(int b: x){
yes.insert({a,b});
yes.insert({b,a});
}
}
for(int a: y){
for(int b: y){
yes.insert({a,b});
yes.insert({b,a});
}
}
};
shuffle(p.begin(),p.end(),rng);
while(!p.empty()){
int i=p.back();
p.pop_back();
if(x.size()==0){
x={i};
continue;
}
if(y.size()==0){
if(conn({i}, {x[0]})){
x.insert(x.begin(),i);
continue;
}
if (conn({i}, {x.back()})){
x.push_back(i);
continue;
}
if(!conn({i}, x)){
y={i};
fix();
continue;
}
int lo=1;
int hi=x.size()-2;
while(lo<hi){
int m=(lo+hi)/2;
vector<int>z;
for(int i=lo;i<=m;i++){
z.push_back(x[i]);
}
if(conn(z, {i})){
hi=m;
} else{
lo=m+1;
}
}
vector<int>z;
for(int i=lo+1;i<x.size();i++){
z.push_back(x[i]);
}
for(int i=0;i<=lo;i++){
z.push_back(x[i]);
}
z.push_back(i);
x=z;
continue;
}
if(!conn(x,{i})){
y.push_back(i);
fix();
continue;
}
if(!conn(y,{i})){
x.push_back(i);
fix();
continue;
}
int i0=0;
int j0=0;
if(!conn({x[0]},{i})){
int lo=1;
int hi=x.size()-1;
while(lo<hi){
int m=(lo+hi)/2;
vector<int>z;
for(int i=lo;i<=m;i++){
z.push_back(x[i]);
}
if(are_connected(z, {i})){
hi=m;
} else{
lo=m+1;
}
}
i0=lo;
} else {
int lo=0;
int hi=y.size()-1;
while(lo<hi){
int m=(lo+hi)/2;
vector<int>z;
for(int i=lo;i<=m;i++){
z.push_back(y[i]);
}
if(are_connected(z, {i})){
hi=m;
} else{
lo=m+1;
}
}
j0=lo;
}
swap(x[i0], x.back());
swap(y[j0], y[0]);
x.push_back(i);
for(int i: y){
x.push_back(i);
}
y={};
}
if(x.size()>y.size()){
return x;
} else{
return y;
}
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:15:48: error: type-specifier invalid in lambda
15 | auto conn = [&](vector<int>x,vector<int>y) bool {
| ^~~~
longesttrip.cpp: In lambda function:
longesttrip.cpp:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | if(c1==x.size()*y.size()){
| ~~^~~~~~~~~~~~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:106:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i=lo+1;i<x.size();i++){
| ~^~~~~~~~~
