제출 #1171473

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

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;


vector<int> longest_trip(int N, int D) {
    if (D == 3) {
        vector<int> ans(N);
        iota(ans.begin(), ans.end(), 0);
        return ans;
    }
    if (D == 2) {
        deque<int> ans;

        vector<int> cl(N, 0);

        if (are_connected({0}, {1})) {
            cl[0] = cl[1] = 1;
            ans.push_front(0); ans.push_back(1);
        } else {
            cl[0] = cl[2] = 1;
            ans.push_front(0); ans.push_back(2);
        }

        while (ans.size() < N) {
            for (int i = 0; i < N; i++)
            if (!cl[i]) {
                if (are_connected({ans.front()}, {i})) ans.push_front(i);
                else ans.push_back(i);
                cl[i] = 1;
                break;
            }
        }

        return vector<int>(ans.begin(), ans.end());
    }

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    vector<int> A(N, 0);
    iota(A.begin(), A.end(), 0);
    shuffle(A.begin(), A.end(), rng);

    vector<int> pathA, pathB;
    pathA.emplace_back(A[0]);
    pathB.emplace_back(A[1]);

    int flag = 0;
    for (int i = 2; i < N; i++)
    if (flag) {
        if (are_connected({pathA.back()}, {A[i]})) {
            pathA.emplace_back(A[i]);
            flag = 0;
        } else {
            flag = 1;
            pathB.emplace_back(A[i]);
        }
    }
    else if (are_connected({pathA.back()}, {pathB.back()})) {
        for (int x = pathB.size()-1; x >= 0; x--) pathA.emplace_back(pathB[x]);
        pathB.assign(1, A[i]);
        flag = 0;
    } else {
        if (are_connected({pathA.back()}, {A[i]})) {
            pathA.emplace_back(A[i]);
            flag = 0;
        } else {
            flag = 1;
            pathB.emplace_back(A[i]);
        }
    }

    if (!are_connected(vector<int>(pathA.begin(), pathA.end()), vector<int>(pathB.begin(), pathB.end()))) return pathA.size() < pathB.size() ? pathB : pathA;

    if (are_connected({pathA.back()}, {pathB.back()})) {
        for (int i = pathB.size()-1; i >= 0; i--) pathA.emplace_back(pathB[i]);
        return pathA;
    }
    if (are_connected({pathA[0]}, {pathB.back()})) {
        reverse(pathA.begin(), pathA.end());
        for (int i = pathB.size()-1; i >= 0; i--) pathA.emplace_back(pathB[i]);
        return pathA;
    }
    int lo, hi;
    lo = -1; hi = pathA.size() - 1;

    while (hi - lo > 1) {
        int mid = (lo + hi) >> 1;
        if (are_connected(vector<int>(pathA.begin(), pathA.begin()+mid+1), pathB)) hi = mid;
        else lo = mid;
    }

    int pA = hi;

    lo = -1; hi = pathB.size() - 1;
    while (hi - lo > 1) {
        int mid = (lo + hi) >> 1;
        if (are_connected({pathA[pA]}, vector<int>(pathB.begin(), pathB.begin()+mid+1))) hi = mid;
        else lo = mid;
    }
    int pB = hi;
    vector<int> ans;
    for (int i = pA + 1; i < pathA.size(); i++) ans.emplace_back(pathA[i]);
    for (int i = 0; i <= pA; i++) ans.emplace_back(pathA[i]);
    for (int i = pB; i < pathB.size(); i++) ans.emplace_back(pathB[i]);
    for (int i = 0; i < pB; i++) ans.emplace_back(pathB[i]);
    return ans;
}

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