Submission #1141043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141043		Luvidi	Longest Trip (IOI23_longesttrip)	C++20	85 / 100	6 ms	508 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> longest_trip(int n, int d)
{
    vector<vector<int>> v;
    for(int i=0;i<n;i++)v.push_back({i});
    while(v.size()>2){
        vector<int> v1,v2,v3;
        v1=v.back();v.pop_back();
        v2=v.back();v.pop_back();
        v3=v.back();v.pop_back();
        if(are_connected({v1[0]},{v2[0]})){
            reverse(v1.begin(),v1.end());
            for(int i:v2)v1.push_back(i);
            v.push_back(v1);
            v.push_back(v3);
        }else if(are_connected({v1[0]},{v3[0]})){
            reverse(v1.begin(),v1.end());
            for(int i:v3)v1.push_back(i);
            v.push_back(v1);
            v.push_back(v2);
        }else{
            reverse(v2.begin(),v2.end());
            for(int i:v3)v2.push_back(i);
            v.push_back(v2);
            v.push_back(v1);
        }
    }
    if(v[0].size()>v[1].size())swap(v[0],v[1]);
    if(are_connected(v[0],v[1])){
        if(are_connected({v[0][0]},{v[1][0]})){
            reverse(v[0].begin(),v[0].end());
            for(int i:v[1])v[0].push_back(i);
            return v[0];
        }else if(are_connected({v[0][0]},{v[1].back()})){
            for(int i:v[0])v[1].push_back(i);
            return v[1];
        }else if(are_connected({v[0].back()},{v[1][0]})){
            for(int i:v[1])v[0].push_back(i);
            return v[0];
        }else if(are_connected({v[0].back()},{v[1].back()})){
            reverse(v[0].begin(),v[0].end());
            for(int i:v[0])v[1].push_back(i);
            return v[1];
        }else{
            int l=0,r=v[0].size()-1;
            while(l<r){
                int m=(l+r)/2;
                vector<int> t;
                for(int i=0;i<=m;i++)t.push_back(v[0][i]);
                if(are_connected(t,v[1]))r=m;
                else l=m+1;
            }
            int i=l;
            l=0,r=v[1].size()-1;
            while(l<r){
                int m=(l+r)/2;
                vector<int> t;
                for(int i=0;i<=m;i++)t.push_back(v[1][i]);
                if(are_connected(t,{v[0][i]}))r=m;
                else l=m+1;
            }
            int j=l;
            vector<int> ans;
            for(int x=i+1;x<v[0].size();x++)ans.push_back(v[0][x]);
            for(int x=0;x<=i;x++)ans.push_back(v[0][x]);
            for(int x=j;x<v[1].size();x++)ans.push_back(v[1][x]);
            for(int x=0;x<j;x++)ans.push_back(v[1][x]);
            return ans;
        }
    }
    return v[1];
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 45 / 60