Submission #839862

#	Time	Username	Problem	Language	Result	Execution time	Memory
839862		tamionv	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	18 ms	308 KiB

longesttrip

#include "longesttrip.h"

#include <bits/stdc++.h>

using namespace std;

mt19937 mt(123);

bool my_are_connected(vector<int> a, vector<int> b) {
    a.erase(unique(begin(a), end(a)), end(a));
    b.erase(unique(begin(b), end(b)), end(b));
    return are_connected(a, b);
}

pair<int, int> cbin(vector<int> as, vector<int> bs) {
    shuffle(begin(as), end(as), mt);
    shuffle(begin(bs), end(bs), mt);

    bool swp = false;

    if (as.size() > bs.size()) {
        swap(as, bs);
        swp = true;
    }
    pair<int, int> ret;

    if (bs.size() == 1)
        ret = make_pair(as[0], bs[0]);
    else {
        vector<int> xs(begin(bs), begin(bs) + bs.size() / 2), ys(begin(bs) + bs.size() / 2, end(bs));

        if (my_are_connected(as, xs))
            ret = cbin(as, xs);
        else
            ret = cbin(as, ys);
    }

    if (swp) swap(ret.first, ret.second);
    return ret;
}

std::vector<int> longest_trip(int N, int D) {
    mt = mt19937(123 + N + D);
    vector<int> perm(N);
    iota(begin(perm), end(perm), 0);
    shuffle(begin(perm), end(perm), mt);

    vector<int> xs = {}, ys = {};

    for (auto x : perm) {
        if (xs.empty())
            xs.push_back(x);
        else if (ys.empty()) {
            if (my_are_connected({x}, {xs.back()}))
                xs.push_back(x);
            else
                ys.push_back(x);
        } else {
            if (bernoulli_distribution(0.5)(mt)) {
                if (!my_are_connected({x}, {xs.back()}))
                    ys.push_back(x);
                else if (!my_are_connected({x}, {ys.back()}))
                    xs.push_back(x);
                else {
                    xs.push_back(x);
                    xs.insert(end(xs), begin(ys), end(ys));
                    ys = {};
                }
            } else {
                if (!my_are_connected({x}, {ys.back()}))
                    xs.push_back(x);
                else if (!my_are_connected({x}, {xs.back()}))
                    ys.push_back(x);
                else {
                    xs.push_back(x);
                    xs.insert(end(xs), begin(ys), end(ys));
                    ys = {};
                }
            }
        }
    }

    vector<int> ret = {};
    if (ys.empty())
        ret = xs;
    else {
        if (!my_are_connected(xs, ys))
            ret = (xs.size() < ys.size() ? ys : xs);
        else if (my_are_connected({xs.front(), xs.back()}, {ys.front(), ys.back()})) {
            auto [x, y] = cbin({xs.front(), xs.back()}, {ys.front(), ys.back()});
            if (xs.back() != x) reverse(begin(xs), end(xs));
            if (ys.front() != y) reverse(begin(ys), end(ys));
            xs.insert(end(xs), begin(ys), end(ys));
            ret = xs;
        } else {
            auto [x, y] = cbin(xs, ys);
            rotate(begin(xs), find(begin(xs), end(xs), x), end(xs));
            rotate(begin(ys), find(begin(ys), end(ys), y), end(ys));
            reverse(begin(xs), end(xs));
            xs.insert(end(xs), begin(ys), end(ys));
            ret = xs;
        }
    }

    return ret;
}

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