Submission #1226608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226608		edga1	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	6 ms	424 KiB

longesttrip

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

vector<int> a[260];

vector<int> longest_trip(int N, int D)
{
    srand(time(0));
    vector<int> v(N);
    for(int i=0; i<N; i++) v[i]=i;
    random_shuffle(v.begin(),v.end());
    vector<int> p1={v[0]},p2={v[1]};
    int c=1,atb;
    for(int i=2; i<N; i++){
        if(c==0){
            atb=are_connected(vector<int>(1,p1.back()),vector<int>(1,v[i]));
            if(atb==1){
                c=1;
                p1.pb(v[i]);
            }
            else p2.pb(v[i]);
        }else{
            atb=are_connected(vector<int>(1,p1.back()),vector<int>(1,v[i]));
            if(atb==1){
                p1.pb(v[i]);
                continue;
            }
            atb=are_connected(vector<int>(1,p2.back()),vector<int>(1,v[i]));
            if(atb==1){
                p2.pb(v[i]);
                c=0;
                continue;
            }
            for(int j=p2.size()-1; j>=0; j--) p1.pb(p2[j]);
            p2.clear();
            p2.pb(v[i]);
        }
    }
    atb=are_connected(p1,p2);
    if(atb==0){
        if(p1.size()>p2.size()) return p1;
        return p2;
    }
    vector<int> g1={p1[0]},g2={p2[0]};
    if(p1.size()>1) g1.pb(p1.back());
    if(p2.size()>1) g2.pb(p2.back());
    atb=are_connected(g1,g2);
    if(atb==1){
        atb=are_connected(vector<int>(1,p1.back()),vector<int>(1,p2[0]));
        if(atb==1){
            for(int i=0; i<p2.size(); i++) p1.pb(p2[i]);
            return p1;
        }
        atb=are_connected(vector<int>(1,p1.back()),vector<int>(1,p2.back()));
        if(atb==1){
            for(int i=p2.size()-1; i>=0; i--) p1.pb(p2[i]);
            return p1;
        }
        atb=are_connected(vector<int>(1,p1[0]),vector<int>(1,p2.back()));
        if(atb==1){
            for(int i=0; i<p1.size(); i++) p2.pb(p1[i]);
            return p2;
        }
        reverse(p1.begin(),p1.end());
        for(int i=0; i<p2.size(); i++) p1.pb(p2[i]);
        return p1;
    }
    int l=0,r=p1.size()-1,mid,s1p,s2p;
    while(l<r){
        mid=(l+r)/2;
        vector<int> temp=vector<int>(p1.begin()+l,p1.begin()+mid+1);
        atb=are_connected(temp,p2);
        if(atb==0) l=mid+1;
        else r=mid;
    }
    s1p=l;
    l=0; r=p2.size();
    while(l<r){
        mid=(l+r)/2;
        vector<int> temp=vector<int>(p2.begin()+l,p2.begin()+mid+1);
        atb=are_connected(temp,p1);
        if(atb==0) l=mid+1;
        else r=mid;
    }
    s2p=l;
    vector<int> rez;
    for(int i=s1p-1; i>=0; i--) rez.pb(p1[i]);
    for(int i=p1.size()-1; i>=s1p; i--) rez.pb(p1[i]);
    for(int i=s2p; i>=0; i--) rez.pb(p2[i]);
    for(int i=p2.size()-1; i>s2p; i--) rez.pb(p2[i]);
    return rez;
}

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