Submission #840731

#	Time	Username	Problem	Language	Result	Execution time	Memory
840731		emeraldblock	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	20 ms	460 KiB

longesttrip

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

#ifndef LOCAL
#define cerr if (false) cerr
#endif

using namespace std;

std::vector<int> longest_trip(int N, int D)
{
    mt19937 mt(123213);
    vector<int> pi;
    pi.resize(N);
    iota(pi.begin(),pi.end(),0);
    // shuffle(pi.begin(),pi.end(),mt);

    auto isline = [&](vector<int> a) {
        for (auto& x : a) x = pi[x];
#ifdef LOCAL
        for (int i = 1; i < a.size(); ++i) {
            assert(are_connected({a[i-1]}, {a[i]}));
        }
#endif
        return a;
    };
    auto check = [&](vector<int> a, vector<int> b) {
        for (auto& x : a) x = pi[x];
        for (auto& x : b) x = pi[x];
        return are_connected(a,b);
    };

    vector<int> path{0};
    vector<vector<int>> cliques;
    for (int i = 1; i < N; ++i) {
        cliques.push_back({i});
    }
    optional<vector<int>> disj;
    while (!cliques.empty()) {
        shuffle(cliques.begin(),cliques.end(),mt);
        auto cand = cliques.back(); cliques.pop_back();
        cerr << path.back() << " : ";
        for (auto x : cand) cerr << x << ", ";
        cerr << "\n";
        if (check({path.back()}, cand)) {
            int lo = 0, hi = cand.size();
            while (hi-lo > 1) {
                int mid = (lo+hi)/2;
                vector<int> v;
                for (int i = lo; i < mid; ++i) {
                    v.push_back(cand[i]);
                }
                if (check({path.back()}, v)) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            }
            swap(cand[0],cand[lo]);
            path.insert(path.end(),cand.begin(),cand.end());
            if (disj) {
                cliques.push_back(*disj);
                disj.reset();
            }
        } else {
            if (disj) {
                auto& v = disj.value();
                v.insert(v.end(),cand.begin(),cand.end());
            } else {
                disj = cand;
            }
        }
    }
    if (!disj) {
        return isline(path);
    }
    vector<int> rest = *disj;
    if (!check(path, rest)) {
        return isline(path.size() >= rest.size() ? path : rest);
    }
    if (check({path.front()},rest)) {
        reverse(path.begin(),path.end());
    } else {
        int lo = 0, hi = path.size();
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            vector<int> v;
            for (int i = mid; i < hi; ++i) {
                v.push_back(path[i]);
            }
            if (check(v, rest)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        rotate(path.begin(),path.begin()+hi,path.end());
    }
    int lo = 0, hi = rest.size();
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;
        vector<int> v;
        for (int i = lo; i < mid; ++i) {
            v.push_back(rest[i]);
        }
        if (check({path.back()}, v)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    rotate(rest.begin(),rest.begin()+lo,rest.end());
    path.insert(path.end(),rest.begin(),rest.end());
    return isline(path);
}

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