Submission #1260781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260781		LittleCube	Longest Trip (IOI23_longesttrip)	C++17	85 / 100	6 ms	524 KiB

longesttrip

#include "longesttrip.h"

#include <chrono>
#include <random>
#include <algorithm>
using namespace std;

std::vector<int> longest_trip(int N, int D)
{
    vector<vector<int>> trips;
    for (int i = 0; i < N; i++)
        trips.emplace_back(vector{i});
    mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(trips.begin(), trips.end(), rd);

    while (trips.size() >= 3)
    {
        vector<vector<int>> last(trips.end() - 3, trips.end());
        trips.resize(trips.size() - (size_t)3);

        if (are_connected({last[0].front()}, {last[2].front()}))
            swap(last[1], last[2]);
        else if (are_connected({last[1].front()}, {last[2].front()}))
            swap(last[0], last[2]);

        reverse(last[0].begin(), last[0].end());
        last[0].insert(last[0].end(), last[1].begin(), last[1].end());
        trips.emplace_back(last[0]);
        trips.emplace_back(last[2]);
    }

    // Case 1: not connected two components
    if (!are_connected(trips[0], trips[1]))
        return trips[0].size() >= trips[1].size() ? trips[0] : trips[1];

    // Case 2: end points directly connecting
    for (auto t = 0; t < 2; t++)
    {
        if (trips[1].size() >= 3 && are_connected({trips[0].back()}, {trips[1].front(), trips[1].back()}))
        {
            if (are_connected({trips[0].back()}, {trips[1].front()}))
                trips[0].insert(trips[0].end(), trips[1].begin(), trips[1].end());
            else
                trips[0].insert(trips[0].end(), trips[1].rbegin(), trips[1].rend());
            return trips[0];
        }
        swap(trips[0], trips[1]);
    }

    // Case 3: two cycles
    auto reduce = [](vector<int> target, vector<int> against) -> int
    {
        while (target.size() > 1)
        {
            size_t mid = target.size() / 2;
            if (are_connected(vector(target.begin(), target.begin() + mid), against))
                target.resize(mid);
            else
                target = vector(target.begin() + mid, target.end());
        }
        return target.front();
    };

    int u = reduce(trips[0], trips[1]);
    int v = reduce(trips[1], {u});
    rotate(trips[0].begin(), find(trips[0].begin(), trips[0].end(), u), trips[0].end());
    rotate(trips[1].begin(), find(trips[1].begin(), trips[1].end(), v), trips[1].end());
    reverse(trips[0].begin(), trips[0].end());
    trips[0].insert(trips[0].end(), trips[1].begin(), trips[1].end());

    return trips[0];
}

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