Submission #1233050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233050		m5588ohammed	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	11 ms	1468 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int n,con[501][501];
bool ask(int i,int j){
    if(con[i][j]!=-1) return con[i][j];
    return con[i][j]=con[j][i]=are_connected({i},{j});
}
vector <int> merge(vector <int> a,vector <int> b){
    for(int j:b) a.push_back(j);
    return a;
}
vector <int> case1(vector <int> a,vector<int> b){
    if(are_connected({a.back()},{b[0]})==1){
        return merge(a,b);
    }
    if(are_connected({a[0]},{b.back()})==1){
        return merge(b,a);
    }
    if(are_connected({a[0]},{b[0]})==1){
        reverse(a.begin(),a.end());
        return merge(a,b);
    }
    if(are_connected({a.back()},{b.back()})==1){
        reverse(a.begin(),a.end());
        return merge(b,a);
    }
    return {};
}
pair <int,int> case2(vector <int> a,vector<int> b){
    int l=0,r=(int)a.size()-1,idx1=0,idx2=0;
    while(l<r){
        int mid=(l+r)/2;
        idx1=mid;
        vector <int> A;
        for(int i=l;i<=mid;i++) A.push_back(i);
        if(are_connected(A,b)==1) r=mid;
        else l=mid+1;
    }
    l=0,r=(int)b.size()-1;
    while(l<r){
        int mid=(l+r)/2;
        idx2=mid;
        vector <int> B;
        for(int i=l;i<=mid;i++) B.push_back(i);
        if(are_connected({idx1},B)==1) r=mid;
        else l=mid+1;
    }
    return {idx1,idx2};
}
vector<int> longest_trip(int N, int D)
{
    n=N;
    memset(con,-1,sizeof con);
    vector <int> a={0},b={1};
    for(int i=2;i<n;i++){
        if(ask(a.back(),b.back())==1){
            reverse(b.begin(),b.end());
            a=merge(a,b);
            b={i};
        }
        else{
            if(ask(a.back(),i)==1) a.push_back(i);
            else b.push_back(i);
        }
    }
    if(are_connected(a,b)==0){
        if(a.size()>b.size()) return a;
        return b;
    }
    vector <int> A={a.back()},B={b.back()};
    if(a.size()>1) A.push_back(a[0]);
    if(b.size()>1) B.push_back(b[0]);
    if(are_connected(A,B)==1) return case1(a,b);
    auto [idx1,idx2]=case2(a,b);
    vector <int> ans;
    for(int i=idx1+1;i<=idx1+((int)a.size());i++) ans.push_back(a[i%((int)a.size())]);
    for(int i=idx2;i<idx2+((int)b.size());i++) ans.push_back(b[i%((int)b.size())]);
    return ans;
}

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