제출 #1058876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058876		AlphaBruh	가장 긴 여행 (IOI23_longesttrip)	C++17	100 / 100	11 ms	764 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
//bool are_connected(std::vector<int> A, std::vector<int> B);
vector<int>A;
vector<int>B;
int al;
int fA(int l, int r, int s=0){
    if(l==r){
        if(s) return l;
        if(are_connected({A[l]},B)) return l;
        return -1;
    }
    int md=(l+r)>>1;
    vector<int>check;
    for(int i=l;i<=md;i++) check.push_back(A[i]);
    if(are_connected(check,B)) return fA(l,md,1);
    return fA(md+1,r,s);
}
int fB(int l, int r){
    if(l==r) return l;
    int md=(l+r)>>1;
    vector<int>check;
    for(int i=l;i<=md;i++) check.push_back(B[i]);
    if(are_connected(check,{A[al]})) return fB(l,md);
    return fB(md+1,r);
}
std::vector<int> longest_trip(int N, int D)
{
    deque<int>a;
    deque<int>b;
    a.push_back(0);
    b.push_back(1);
    bool snc=0;
    for(int i=2;i<N;i++){
        if(snc==0){
            bool ac = are_connected({a.front()},{i});
            if(ac){
                a.push_front(i);
                snc=0;
                continue;
            }
            bool bc = are_connected({b.front()},{i});
            if(bc){
                b.push_front(i);
                snc=1;
                continue;
            }
            while(b.size()){
                a.push_front(b.front());
                b.pop_front();
            }
            b.push_front(i);
            snc=0;
            continue;
        }
        bool ac = are_connected({a.front()},{i});
        if(ac){
            a.push_front(i);
            snc=0;
            continue;
        }
        b.push_front(i);
        snc=1;
        continue;
    }
    vector<int>afb;
    vector<int>bfb;
    afb.push_back(a.front());
    if(a.front()!=a.back()) afb.push_back(a.back()); 
    bfb.push_back(b.front());
    if(b.front()!=b.back()) bfb.push_back(b.back());
    if(are_connected(afb,bfb)){
        if(are_connected({a.front()},{b.front()})){
            while(b.size()){
                a.push_front(b.front());
                b.pop_front();
            }
        }
        else if(are_connected({a.front()},{b.back()})){
            while(b.size()){
                a.push_front(b.back());
                b.pop_back();
            }
        }else if(are_connected({a.back()},{b.front()})){
            while(b.size()){
                a.push_back(b.front());
                b.pop_front();
            }
        }
        else{
            while(b.size()){
                a.push_back(b.back());
                b.pop_back();
            }
        }
        vector<int>ret;
        while(a.size()){
            ret.push_back(a.front());
            a.pop_front();
        }
        return ret;
    }
    A.clear();
    B.clear();
    while(a.size()){
        A.push_back(a.front());
        a.pop_front();
    }
    while(b.size()){
        B.push_back(b.front());
        b.pop_front();
    }
    al = fA(0,A.size()-1,0);
    if(al==-1) return A.size()>B.size()?A:B;
    int bl = fB(0,B.size()-1);
    int as = A.size(),bs=B.size();
    vector<int>ret;
    for(int i=(al+1)%as;i!=al;i=(i+1)%as){
        ret.push_back(A[i]);
    }
    ret.push_back(A[al]);
    ret.push_back(B[bl]);
    for(int i=(bl+1)%bs;i!=bl;i=(i+1)%bs){
        ret.push_back(B[i]);
    }
    return ret;
}

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