Submission #1214596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214596		trimkus	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	1101 ms	525860 KiB

longesttrip

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

using namespace std;
int N;
const int MAXN = 256;
vector<int> adj[MAXN];


void connect(vector<int>& path1, vector<int>& path2) {
    reverse(begin(path2), end(path2));
    for (int j = 0; j < (int)path2.size(); ++j) {
        path1.push_back(path2[j]);
    }
    path2.clear();
}

std::vector<int> longest_trip(int _N, int D)
{
    N = _N;
    vector<int> idx(N);
    iota(begin(idx), end(idx), 0);
    mt19937 rng(0);
    // shuffle(begin(idx), end(idx), rng);
    vector<int> path1{idx[0]}, path2{idx[1]};
    for (int j = 2; j < N; ++j) {
        int i = idx[j];
        if (are_connected({path1.back()}, {i})) {
            path1.push_back(i);
        } else if (are_connected({path2.back()}, {i})) {
            path2.push_back(i);
        } else {
            assert(are_connected({path1.back()}, {path2.back()}));
            connect(path1, path2);
            path2.push_back(i);
        }
    }
    if (path1.size() < path2.size()) swap(path1, path2);
    if (path2.size() == 0) return path1;
    if (are_connected({path1.back()}, {path2.back()})) {
        connect(path1, path2);
        return path1;
    }
    reverse(begin(path1), end(path1));
    if (are_connected({path1.back()}, {path2.back()})) {
        connect(path1, path2);
        return path1;
    }
    reverse(begin(path1), end(path1));
    reverse(begin(path2), end(path2));
    if (are_connected({path1.back()}, {path2.back()})) {
        connect(path1, path2);
        return path1;
    }
    reverse(begin(path1), end(path1));
    if (are_connected({path1.back()}, {path2.back()})) {
        connect(path1, path2);
        return path1;
    }
    reverse(begin(path1), end(path1));
    reverse(begin(path2), end(path2));
    cerr << "Path1 = ";
    for (auto& u : path1) {
        cerr << u << " ";
    }
    cerr << "\nPath2 = ";
    for (auto& u : path2) {
        cerr << u << " ";
    }
    cerr << "\n";
    if (N <= 20) {
        for (int i = 0; i < (int)path1.size(); ++i) {
            for (int j = 0; j < (int)path2.size(); ++j) {
                if (are_connected({path1[i]}, {path2[j]})) {
                    cerr << "Found a connection = " << path1[i] << " " << path2[j] << "\n";
                    vector<int> super_path;
                    int ni = (i + 1) % (int)path1.size();
                    while (ni != i) {
                        super_path.push_back(path1[ni]);
                        ni = (ni + 1) % (int)path1.size();
                    }
                    super_path.push_back(path1[i]);
                    super_path.push_back(path2[j]);
                    int nj = (j + 1) % (int)path2.size();
                    while (nj != j) {
                        super_path.push_back(path2[nj]);
                        nj = (nj + 1) % (int)path2.size();
                    }
                    cerr << "Cycle len = " << super_path.size() << "\n";
                    // reverse(begin(super_path), end(super_path));
                    return super_path;
                }
            }
        }
        return path1;
    }
    vector<int> super_path;
    int l1 = 0, r1 = (int)path1.size();
    int l2 = 0, r2 = (int)path2.size();
    while (r1 - l1 > 1) {
        int m1 = (l1 + r1) / 2;
        if (are_connected(vector<int>(begin(path1) + l1, begin(path1) + r1),
            vector<int>(begin(path2) + l2, begin(path2) + r2))) {
            r1 = m1;
        } else {
            l1 = m1;
        }
    }
    while (r2 - l2 > 1) {
        int m2 = (l2 + r2) / 2;
        if (are_connected(vector<int>(begin(path1) + l1, begin(path1) + r1),
            vector<int>(begin(path2) + l2, begin(path2) + r2))) {
            r2 = m2;
        } else {
            l2 = m2;
        }
    }
    int ni = (r1 + 1) % (int)path1.size();
    while (ni != r1) {
        super_path.push_back(path1[ni]);
        ni = (ni + 1) % (int)path1.size();
    }
    super_path.push_back(path1[r1]);
    super_path.push_back(path2[r2]);
    ni = (r2 + 1) % (int)path2.size();
    while (ni != r2) {
        super_path.push_back(path2[ni]);
        ni = (ni + 1) % (int)path2.size();
    }
    return super_path;
}

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