제출 #1144835

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144835		Math4Life2020	가장 긴 여행 (IOI23_longesttrip)	C++20	100 / 100	7 ms	484 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>; using vi = vector<ll>;

vector<ll> longest_trip(ll N, ll D) {
    vector<ll> va = {0}; bool conA = 0;
    vector<ll> vb = {1}; bool conB = 0;
    queue<ll> rnum;
    vector<ll> vy,vn; //connected: yes, no
    ll x0; //current center
    for (ll i=2;i<N;i++) {
        rnum.push(i);
    }
    while (!rnum.empty()) {
        vy.clear(); vn.clear();
        x0 = rnum.front(); rnum.pop();
        conA = are_connected((vi){va[0]},(vi){x0});
        conB = are_connected((vi){vb[0]},(vi){x0});
        if (conA&&conB) {
            vector<ll> van;
            for (ll i=(va.size()-1);i>=0;i--) {
                van.push_back(va[i]);
            }
            van.push_back(x0);
            for (ll i=0;i<(vb.size());i++) {
                van.push_back(vb[i]);
            }
            va = van;
            vb.clear();
            if (rnum.empty()) {
                break;
            }
            vb.push_back(rnum.front()); rnum.pop();
            continue;
        }
        while ((((ll)conA)+((ll)conB)+vy.size())<2 && !rnum.empty()) {
            ll x1 = rnum.front(); rnum.pop();
            if (are_connected((vi){x1},(vi){x0})) {
                vy.push_back(x1);
            } else {
                vn.push_back(x1);
            }
        }
        if (conA) {
            vector<ll> van = vy;
            van.push_back(x0);
            vector<ll> vbn = vn;
            for (ll x2: va) {
                van.push_back(x2);
            }
            for (ll x2: vb) {
                vbn.push_back(x2);
            }
            va = van; vb = vbn;
        } else if (conB) {
            vector<ll> van = vy;
            van.push_back(x0);
            vector<ll> vbn = vn;
            for (ll x2: vb) {
                van.push_back(x2);
            }
            for (ll x2: va) {
                vbn.push_back(x2);
            }
            va = van; vb = vbn;
        } else {
            assert(!conB && !conA);
            vector<ll> van;
            for (ll i=(vb.size()-1);i>=0;i--) {
                van.push_back(vb[i]);
            }
            for (ll x2: vn) {
                van.push_back(x2);
            }
            for (ll i=0;i<va.size();i++) {
                van.push_back(va[i]);
            }
            va = van;
            if (vy.size()==2) {
                vb = (vi){vy[0],x0,vy[1]};
            } else if (vy.size()==1) {
                vb = (vi){vy[0],x0};
            } else {
                assert(vy.size()==0);
                vb = (vi){x0};
            }
        }
    }
    assert(va.size()+vb.size()==N);
    if (va.size()==0) {
        return vb;
    }
    if (vb.size()==0) {
        return va;
    }
    if (va.size()<vb.size()) {
        swap(va,vb);
    }
    //thus va size >= vb size -> va size >= 2
    if (are_connected((vi){va[0]},(vi){vb[0]})) {
        vector<ll> vf;
        for (ll i=(va.size()-1);i>=0;i--) {
            vf.push_back(va[i]);
        }
        for (ll i=0;i<vb.size();i++) {
            vf.push_back(vb[i]);
        }
        return vf;
    }
    if (are_connected((vi){va[0]},(vi){vb[vb.size()-1]})) {
        vector<ll> vf;
        for (ll i=(va.size()-1);i>=0;i--) {
            vf.push_back(va[i]);
        }
        for (ll i=(vb.size()-1);i>=0;i--) {
            vf.push_back(vb[i]);
        }
        return vf;
    }
    //flip va
    if (are_connected((vi){va[va.size()-1]},(vi){vb[0]})) {
        vector<ll> vf;
        for (ll i=0;i<va.size();i++) {
            vf.push_back(va[i]);
        }
        for (ll i=0;i<vb.size();i++) {
            vf.push_back(vb[i]);
        }
        return vf;
    }
    if (are_connected((vi){va[va.size()-1]},(vi){vb[vb.size()-1]})) {
        vector<ll> vf;
        for (ll i=0;i<va.size();i++) {
            vf.push_back(va[i]);
        }
        for (ll i=(vb.size()-1);i>=0;i--) {
            vf.push_back(vb[i]);
        }
        return vf;
    }
    //now both sequences are cyclized
    if (!are_connected(va,vb)) {
        if (va.size()<vb.size()) {
            return vb;
        } else {
            return va;
        }
    }

    ll xmin = 0; ll xmax = va.size()-1;
    while (xmin<xmax) {
        ll xt = (xmin+xmax)/2;
        vector<ll> vqry;
        for (ll x0=xmin;x0<=xt;x0++) {
            vqry.push_back(va[x0]);
        }
        if (are_connected(vqry,vb)) {
            xmax = xt;
        } else {
            xmin = xt+1;
        }
    }

    vi va1 = {va[xmin]};
    ll ymin = 0; ll ymax = vb.size()-1;
    while (ymin<ymax) {
        ll yt = (ymin+ymax)/2;
        vector<ll> vqry;
        for (ll y0=ymin;y0<=yt;y0++) {
            vqry.push_back(vb[y0]);
        }
        if (are_connected(va1,vqry)) {
            ymax = yt;
        } else {
            ymin = yt+1;
        }
    }

    vector<ll> vfin;
    for (ll i=0;i<(vb.size());i++) {
        vfin.push_back(vb[(i+1+ymin)%vb.size()]);
    }
    for (ll i=0;i<va.size();i++) {
        vfin.push_back(va[(i+xmin)%va.size()]);
    } 
    return vfin;
    // if (are_connected((vi)va[va.size()-1],vb)) {
    //     //binary search for vb first location
    //     vi AP = {va[va.size()-1]};
    //     ll xmin = 0; ll xmax = vb.size()-1;
    //     while (xmin<xmax) {
    //         ll xt = (xmin+xmax)/2;
    //         vector<ll> vqry;
    //         for (ll x0=xmin;x0<=xt;x0++) {
    //             vqry.push_back(vb[xt]);
    //         }
    //         if (are_connected(AP,vqry)) {
    //             xmax = xt;
    //         } else {
    //             xmin = xt+1;
    //         }
    //     }
    //     vector<ll> vf = va;
    //     for (ll x0=0;x0<vb.size();x0++) {
    //         vf.push_back(vb[(x0+xmin)%(vb.size())]);
    //     }
    //     return vf;
    // }

}

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