제출 #1220837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220837		HappyCapybara	Longest Trip (IOI23_longesttrip)	C++17	85 / 100	5 ms	420 KiB

longesttrip

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

vector<int> longest_trip(int N, int D){
    vector<int> p1 = {0}, p2 = {1};
    for (int i=2; i<N; i++){
    if (are_connected({i}, {p1.back()})) p1.push_back(i);
    else if (are_connected({i}, {p2.back()})) p2.push_back(i);
    else {
        while (!p1.empty()){
            p2.push_back(p1.back());
            p1.pop_back();
        }
        p1 = {i};
        }
    }
    if (!are_connected(p1, p2)) return p1.size() > p2.size() ? p1 : p2;
    for (int i=0; i<4; i++){
        if (are_connected({p1.back()}, {p2[0]})){
            for (int x : p2) p1.push_back(x);
            return p1;
        }
        reverse(p2.begin(), p2.end());
        if (i % 2) reverse(p1.begin(), p1.end());
    }
    int l = 0, r = p1.size();
    while (l < r-1){
        int m = (l+r)/2;
        vector<int> v;
        for (int i=m; i<(int)p1.size(); i++) v.push_back(p1[i]);
        if (are_connected(v, p2)) l = m;
        else r = m;
    }
    int a = l;
    l = 0, r = p2.size();
    while (l < r-1){
        int m = (l+r)/2;
        vector<int> v;
        for (int i=m; i<(int)p2.size(); i++) v.push_back(p2[i]);
        if (are_connected(v, {p1[a]})) l = m;
        else r = m;
    }
    int b = l;
    vector<int> np;
    for (int i=(a+1)%(int)p1.size(); ; i = (i+1)%(int)p1.size()){
        np.push_back(p1[i]);
        if (i == a) break;
    }
    for (int i=b; ; i = (i+1)%(int)p2.size()){
        if (i == b && np.size() != p1.size()) break;
        np.push_back(p2[i]);
    }
    return np;
}

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