Submission #1238142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238142		SamAnd	Longest Trip (IOI23_longesttrip)	C++20	85 / 100	7 ms	440 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);

std::vector<int> longest_trip(int N, int D)
{
    int n = N;
    vector<int> t;
    for (int x = 0; x < n; ++x)
        t.push_back(x);
    for (int i = n - 1; i >= 0; --i)
        swap(t[i], t[rnd() % (i + 1)]);

    vector<int> v1;
    vector<int> v2;
    v1.push_back(t[0]);
    v2.push_back(t[1]);
    for (int i = 2; i < n; ++i)
    {
        int x = t[i];
        if (are_connected(vector<int>{x}, vector<int>{v1.back()}))
            v1.push_back(x);
        else if (are_connected(vector<int>{x}, vector<int>{v2.back()}))
            v2.push_back(x);
        else
        {
            reverse(all(v2));
            for (int i = 0; i < sz(v2); ++i)
                v1.push_back(v2[i]);
            v2.clear();
            v2.push_back(x);
        }
    }

    if (are_connected(vector<int>{v1.back()}, vector<int>{v2.back()}))
    {
        reverse(all(v2));
        for (int i = 0; i < sz(v2); ++i)
            v1.push_back(v2[i]);
        v2.clear();
        return v1;
    }
    reverse(all(v1));
    if (are_connected(vector<int>{v1.back()}, vector<int>{v2.back()}))
    {
        reverse(all(v2));
        for (int i = 0; i < sz(v2); ++i)
            v1.push_back(v2[i]);
        v2.clear();
        return v1;
    }
    reverse(all(v2));
    if (are_connected(vector<int>{v1.back()}, vector<int>{v2.back()}))
    {
        reverse(all(v2));
        for (int i = 0; i < sz(v2); ++i)
            v1.push_back(v2[i]);
        v2.clear();
        return v1;
    }
    reverse(all(v1));
    if (are_connected(vector<int>{v1.back()}, vector<int>{v2.back()}))
    {
        reverse(all(v2));
        for (int i = 0; i < sz(v2); ++i)
            v1.push_back(v2[i]);
        v2.clear();
        return v1;
    }

    if (!are_connected(v1, v2))
    {
        if (sz(v2) > sz(v1))
            swap(v1, v2);
        return v1;
    }

    int x = -1;
    int l = 0, r = sz(v1) - 1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        vector<int> u;
        for (int i = 0; i <= m; ++i)
            u.push_back(v1[i]);
        if (are_connected(u, v2))
        {
            x = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }
    assert(x != -1);

    int y = -1;
    l = 0, r = sz(v2) - 1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        vector<int> u;
        for (int i = 0; i <= m; ++i)
            u.push_back(v2[i]);
        if (are_connected(u, vector<int>{v1[x]}))
        {
            y = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }
    assert(y != -1);

    vector<int> u;
    for (int i = 0; i < sz(v1); ++i)
    {
        u.push_back(v1[(x + 1 + i) % sz(v1)]);
    }
    for (int i = 0; i < sz(v2); ++i)
    {
        u.push_back(v2[(y + i) % sz(v2)]);
    }
    return u;
}

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