Submission #1235107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235107		guagua0407	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	8 ms	428 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()

std::vector<int> longest_trip(int n, int D)
{
    deque<int> a,b;
    vector<int> ord(n);
    for(int i=0;i<n;i++){
        ord[i]=i;
    }
    mt19937 rng(time(NULL));
    shuffle(all(ord),rng);
    a.push_back(ord[0]);
    b.push_back(ord[1]);
    bool con=false;
    for(int t=2;t<n;t++){
        int i=ord[t];
        int x=a.back();
        int y=b.back();
        if(are_connected({x},{i})){
            a.push_back(i);
            con=false;
        }
        else if(con or are_connected({y},{i})){
            b.push_back(i);
            con=true;
        }
        else{
            while(!b.empty()){
                a.push_back(b.back());
                b.pop_back();
            }
            b.push_back(i);
            con=false;
        }
    }
    if((int)a.size()<(int)b.size()) swap(a,b);
    if(b.empty()){
        vector<int> tmp(a.size());
        for(int i=0;i<(int)a.size();i++) tmp[i]=a[i];
        return tmp;
    }
    if(are_connected({b[0]},{a[0]})){
        while(!b.empty()){
            a.push_front(b[0]);
            b.pop_front();
        }
    }
    else if(are_connected({b[0]},{a.back()})){
        while(!b.empty()){
            a.push_back(b[0]);
            b.pop_front();
        }
    }
    else if(are_connected({b.back()},{a[0]})){
        while(!b.empty()){
            a.push_front(b.back());
            b.pop_back();
        }
    }
    else if(are_connected({b.back()},{a.back()})){
        while(!b.empty()){
            a.push_back(b.back());
            b.pop_back();
        }
    }
    else{
        {
            vector<int> A(a.size()),B(b.size());
            for(int i=0;i<(int)a.size();i++) A[i]=a[i];
            for(int i=0;i<(int)b.size();i++) B[i]=b[i];
            if(!are_connected(A,B)) return A;
        }
        int l=0,r=(int)b.size()-1;
        int tl=0,tr=(int)a.size()-1;
        while(l<r or tl<tr){
            if(l<r){
                int mid=(l+r)/2;
                vector<int> B;
                for(int i=0;i<=mid;i++){
                    B.push_back(b[i]);
                }
                vector<int> tmp;
                for(int i=0;i<=tr;i++) tmp.push_back(a[i]);
                if(are_connected(B,tmp)){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            if(tl<tr){
                int mid=(tl+tr)/2;
                vector<int> A;
                for(int i=0;i<=mid;i++){
                    A.push_back(a[i]);
                }
                vector<int> tmp;
                for(int i=0;i<=r;i++) tmp.push_back(b[i]);
                if(are_connected(A,tmp)){
                    tr=mid;
                }
                else{
                    tl=mid+1;
                }
            }
        }
        int pos=l,pos2=tl;
        deque<int> tmp;
        for(int i=pos2+1;i<(int)a.size();i++) tmp.push_back(a[i]);
        for(int i=0;i<=pos2;i++) tmp.push_back(a[i]);
        for(int i=pos;i>=0;i--) tmp.push_back(b[i]);
        for(int i=(int)b.size()-1;i>pos;i--) tmp.push_back(b[i]);
        swap(tmp,a);
    }
    {
        vector<int> tmp(a.size());
        for(int i=0;i<(int)a.size();i++) tmp[i]=a[i];
        return tmp;
    }
}

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