#include"longesttrip.h"
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int n,miss;
int perm[1000];
vector<pair<int,int>>unc; // not connected
map<pair<int,int>,bool>cache;
vector<int>per(vector<int>arr){
for(int&i:arr)
i=perm[i];
return arr;
}
bool connected(vector<int>a,vector<int>b){
bool res=are_connected(per(a),per(b));
miss+=!res;
return res;
}
bool connected(int a,int b){
if(a>b)
swap(a,b);
if(cache.count({a,b}))
return cache[{a,b}];
return cache[{a,b}]=connected(vector<int>({a}),vector<int>({b}));
}
pair<int,int>find_conn(vector<int>v1,vector<int>v2){
int l1=0,r1=(int)v1.size();
while(l1<r1-1){
int mid=(l1+r1)/2;
vector<int>v;
for(int i=l1;i<mid;i++)
v.push_back(v1[i]);
if(connected(v,v2))
r1=mid;
else
l1=mid;
}
int l2=0,r2=(int)v2.size();
while(l2<r2-1){
int mid=(l2+r2)/2;
vector<int>v;
for(int i=l2;i<mid;i++)
v.push_back(v2[i]);
if(connected({v1[l1]},v))
r2=mid;
else
l2=mid;
}
return{v1[l1],v2[l2]};
}
vector<int>merge(vector<int>v1,vector<int>v2){
while(v2.size()){
v1.push_back(v2.back());
v2.pop_back();
}
return v1;
}
bool is_cached(int a,int b){
return(cache.count({a,b})+cache.count({b,a}))!=0;
}
pair<vector<int>,vector<int>>merge(vector<int>v1,vector<int>v2,vector<int>v3){
int num=is_cached(v1.back(),v2.back())+is_cached(v1.back(),v3.back())+is_cached(v2.back(),v3.back());
if(num==2){
if(!is_cached(v1.back(),v2.back()))
return{merge(v1,v2),v3};
if(!is_cached(v2.back(),v3.back()))
return{merge(v3,v2),v1};
if(!is_cached(v1.back(),v3.back()))
return{merge(v1,v3),v2};
}
if(connected(v1.back(),v2.back()))
return{merge(v1,v2),v3};
unc.emplace_back(v1.back(),v2.back());
if(is_cached(v1.back(),v3.back())||connected(v2.back(),v3.back()))
return{merge(v2,v3),v1};
unc.emplace_back(v2.back(),v3.back());
return{merge(v1,v3),v2};
}
vector<int>cyclic_shift(vector<int>arr,int a){
// it ends with a
vector<int>res;
bool b1=false;
for(int i:arr){
if(b1)
res.push_back(i);
if(i==a)
b1=true;
}
bool b2=true;
for(int i:arr){
if(b2)
res.push_back(i);
if(i==a)
b2=false;
}
return res;
}
vector<int>longest_trip(int N,int D){
miss=0;
cache.clear();
srand(647328);
n=N;
unc.clear();
for(int i=0;i<n;i++)
perm[i]=i;
for(int i=0;i<n;i++)
swap(perm[i],perm[rand()%n]);
vector<vector<int>>arr;
for(int i=0;i<n;i++)
arr.push_back({i});
while(arr.size()>2){
vector<int>v1,v2,v3;
v1=arr.back();
arr.pop_back();
v2=arr.back();
arr.pop_back();
v3=arr.back();
arr.pop_back();
auto res=merge(v1,v2,v3);
arr.insert(arr.begin(),res.first);
arr.insert(arr.begin(),res.second);
}
//cout<<"MISSES: "<<miss<<"\n";
vector<int>res1=arr[0];
vector<int>res2=arr[1];
if(!connected(res1,res2)){
if(res1.size()>res2.size())
return per(res1);
else
return per(res2);
}
/*if(connected(res1.back(),res2.back()))
return per(merge(res1,res2));
reverse(res1.begin(),res1.end());
if(connected(res1.back(),res2.back()))
return per(merge(res1,res2));
reverse(res2.begin(),res2.end());
if(connected(res1.back(),res2.back()))
return per(merge(res1,res2));
reverse(res1.begin(),res1.end());
if(connected(res1.back(),res2.back()))
return per(merge(res1,res2));*/
vector<bool>in_res1(n);
for(int i:res1)
in_res1[i]=true;
// both must be cyclical then
pair<int,int>pr={-1,-1};
for(auto[u,v]:unc){
if(in_res1[u]==in_res1[v]){
if(in_res1[u]){
if(connected(res2[0],u)){
pr={u,res2[0]};
}else{
pr={v,res2[0]};
}
}else{
if(connected(res1[0],u)){
pr={res1[0],u};
}else{
pr={res1[0],v};
}
}
break;
}
}
if(pr.first==-1){
//cout<<"FINDING\n";
pr=find_conn(res1,res2);
}
vector<int>r1=cyclic_shift(res1,pr.first);
vector<int>r2=cyclic_shift(res2,pr.second);
return per(merge(r1,r2));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
344 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
344 KB |
Output is correct |
| 2 |
Correct |
8 ms |
344 KB |
Output is correct |
| 3 |
Correct |
9 ms |
344 KB |
Output is correct |
| 4 |
Correct |
9 ms |
344 KB |
Output is correct |
| 5 |
Correct |
7 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
344 KB |
Output is correct |
| 2 |
Correct |
8 ms |
344 KB |
Output is correct |
| 3 |
Correct |
9 ms |
344 KB |
Output is correct |
| 4 |
Correct |
7 ms |
344 KB |
Output is correct |
| 5 |
Correct |
7 ms |
344 KB |
Output is correct |
| 6 |
Correct |
11 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Incorrect |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
344 KB |
Output is correct |
| 2 |
Correct |
12 ms |
344 KB |
Output is correct |
| 3 |
Correct |
10 ms |
344 KB |
Output is correct |
| 4 |
Correct |
12 ms |
344 KB |
Output is correct |
| 5 |
Correct |
9 ms |
344 KB |
Output is correct |
| 6 |
Correct |
15 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Incorrect |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
344 KB |
Output is correct |
| 2 |
Correct |
11 ms |
344 KB |
Output is correct |
| 3 |
Correct |
8 ms |
344 KB |
Output is correct |
| 4 |
Correct |
12 ms |
344 KB |
Output is correct |
| 5 |
Correct |
9 ms |
496 KB |
Output is correct |
| 6 |
Correct |
8 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
344 KB |
Incorrect |
| 8 |
Halted |
0 ms |
0 KB |
- |
