제출 #1233042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233042		m5588ohammed	가장 긴 여행 (IOI23_longesttrip)	C++20	5 / 100	11 ms	1440 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=a.size()-1,idx1=0,idx2=0;
    while(l<=r){
        int mid=(l+r)/2;
        vector <int> A;
        for(int i=l;i<=mid;i++) A.push_back(i);
        if(are_connected(A,b)==1){
            idx1=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    l=0,r=b.size()-1;
    while(l<=r){
        int mid=(l+r)/2;
        vector <int> B;
        for(int i=l;i<=mid;i++) B.push_back(i);
        if(are_connected({idx1},B)==1){
            idx2=mid;
            r=mid-1;
        }
        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){
            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: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60