| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1209850 | user736482 | 가장 긴 여행 (IOI23_longesttrip) | C++20 | 0 ms | 0 KiB |
#include "longesttrip.h"
stack<ll>mrg(stack<ll>a,stack<ll>b){
while(b.size()){
a.push(b.top());b.pop();
}
return a;
}
vector<ll> longest_trip(ll n,ll smiec){
vector<ll>v;
for(ll i=0;i<n;i++){
v.pb(i);
}
for(ll i=0;i<n;i++){
swap(v[i],v[n-1-rand()%(n-i)]);
}
stack<ll>st,st2;
st.push(v.back());
v.pop_back();
bool bl=1;
for(ll i : v){
/*if(st2.empty()){
if(are_connected({i},{st.top()})){
st.push(i);
}
else{
st2.push(i);
}
}
else{
if(!are_connected({i},{st2.top()})){
st.push(i);
}
else{
if(are_connected({i},{st.top()})){
st.push(i);
while(st2.size()){
st.push(st2.top());
st2.pop();
}
}
else{
st.push(i);
}
}
}*/
if(bl){
if(are_connected({i},{st.top()})){
st.push(i);
bl=0;
}
else{
st2.push(i);
}
}
else{
if(are_connected({i},{st.top()})){
st.push(i);
}
else{
if(st2.size() && are_connected({i},{st2.top()})){
st2.push(i);
bl=1;
}
else{
if(st2.size()==1)bl=1;
st=mrg(st,st2);
while(st2.size())st2.pop();
st2.push(i);
}
}
}
}
vector<ll>v1,v2,V1,V2;
while(st.size()){
v1.pb(st.top());
// cout<<v1.back()<<" ";
st.pop();
}//cout<<"\n";
while(st2.size()){
v2.pb(st2.top());
cout<<v2.back();
st2.pop();
}//cout<<"\n\n";
V1=v1;
V2=v2;
if(v1.empty() || v2.empty() || !are_connected(v1,v2)){
if(v1.size()>v2.size())return v1;
return v2;
}
if(v1.size()>1 && !are_connected({v1[0]},{v1.back()})){
if(!are_connected({v1.back()},{v2[0]}))reverse(v1.begin(),v1.end());
for(ll i : v2)v1.pb(i);
return v1;
}
swap(v1,v2);
if(v1.size()>1 && !are_connected({v1[0]},{v1.back()})){
if(!are_connected({v1.back()},{v2[0]}))reverse(v1.begin(),v1.end());
for(ll i : v2)v1.pb(i);
return v1;
}
vector<ll>v3;
while(v1.size()>1){
while(v1.size()>v3.size()){
v3.pb(v1.back());
v1.pop_back();
}
if(!are_connected(v1,v2))swap(v1,v3);
v3.clear();
}
swap(v1,v2);
while(v1.size()>1){
while(v1.size()>v3.size()){
v3.pb(v1.back());
v1.pop_back();
}
if(!are_connected(v1,v2))swap(v1,v3);
v3.clear();
}
ll poz1;
for(poz1=0;poz1<V1.size();poz1++){
if(V1[poz1]==v1[0])break;
}
ll poz2;
for(poz2=0;poz2<V2.size();poz2++){
if(V2[poz2]==v2[0])break;
}
vector<ll>ans;
for(ll i=poz1+1;i<poz1+V1.size();i++)ans.pb(V1[i%V1.size()]);
ans.pb(v1[0]);
ans.pb(v2[0]);
for(ll i=poz2+1;i<poz2+V2.size();i++)ans.pb(V2[i%V2.size()]);
return ans;
}