Submission #1206538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206538		Nelt	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	5 ms	428 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

std::vector<int> longest_trip(int n, int d)
{
    vector<int> ans;
    vector<int> comp, comp1;
    ll p[n];
    iota(p, p + n, 0);
    shuffle(p, p + n, rng);
    bool idk = true;
    for (int i : p)
        if (comp1.empty())
        {
            if (comp.empty())
            {
                comp = {i};
                continue;
            }
            if (!are_connected({comp.back()}, {i}))
                comp1 = {i}, idk = false;
            else
                comp.push_back(i);
        }
        else if (comp.empty())
        {
            if (!are_connected({comp1.back()}, {i}))
                comp = {i}, idk = false;
            else
                comp1.push_back(i);
        }
        else
        {
            bool ok = are_connected({comp.back()}, {i});
            if (ok)
                comp.push_back(i), idk = true;
            else
            {
                if (!idk) comp1.push_back(i), idk = false;
                else
                {
                    if (are_connected({comp1.back()}, {i})) comp1.push_back(i), idk = false;
                    else
                    {
                        for (ll i = comp1.size() - 1; i >= 0; i--) comp.push_back(comp1[i]);
                        comp1 = {i};
                        idk = true;
                    }
                }
            }
        }
    if (comp1.empty())
        return comp;
    if (comp.size() > comp1.size())
        swap(comp, comp1);
    if (!are_connected(comp, comp1))
        return comp1;
    if (comp1.size() >= 3)
    {
        bool ok;
        if (comp.size() >= 3)
        {
            ok = are_connected({comp.front()}, {comp.back()});
            if (!ok)
            {
                ans = comp;
                if (!are_connected({comp.back()}, {comp1.front()}))
                    reverse(ans.begin(), ans.end());
                for (ll i : comp1)
                    ans.push_back(i);
                return ans;
            }
        }
        swap(comp, comp1);
        if (comp.size() >= 3)
        {
            ok = are_connected({comp.front()}, {comp.back()});
            if (!ok)
            {
                ans = comp;
                if (!are_connected({comp.back()}, {comp1.front()}))
                    reverse(ans.begin(), ans.end());
                for (ll i : comp1)
                    ans.push_back(i);
                return ans;
            }
        }
        swap(comp, comp1);
    }
    ll l = 0, r = comp.size() - 1;
    int first = comp.size() - 1;
    vector<int> tmp;
    while (l <= r)
    {
        tmp.clear();
        ll mid = (l + r) >> 1;
        for (ll i = 0; i <= mid; i++)
            tmp.push_back(comp[i]);
        if (are_connected(tmp, comp1))
            r = mid - 1, first = mid;
        else
            l = mid + 1;
    }
    l = 0, r = comp1.size() - 1;
    int second = comp1.size() - 1;
    while (l <= r)
    {
        tmp.clear();
        ll mid = (l + r) >> 1;
        for (ll i = 0; i <= mid; i++)
            tmp.push_back(comp1[i]);
        if (are_connected({comp[first]}, tmp))
            r = mid - 1, second = mid;
        else
            l = mid + 1;
    }
    for (ll i = first + comp.size() - 1; i >= first; i--)
        ans.push_back(comp[i % comp.size()]);
    for (ll i = second; i < second + comp1.size(); i++)
        ans.push_back(comp1[i % comp1.size()]);
    return ans;
}

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