Submission #846413

#	Time	Username	Problem	Language	Result	Execution time	Memory
846413		Sorting	Longest Trip (IOI23_longesttrip)	C++17	85 / 100	15 ms	1124 KiB

longesttrip

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

using namespace std;

int n, d;

vector<vector<int>> paths;

vector<int> longest_trip(int _n, int _d){
    n = _n, d = _d;

    paths.clear();
    for(int i = 0; i < n; ++i)
        paths.push_back({i});

    mt19937 mt(34234);

    while(paths.size() > 2){
        int sz = paths.size();

        shuffle(paths.begin(), paths.end(), mt);

        if(sz == 3){
            vector<int> t{sz - 1, sz - 2, sz - 3};

            bool ok = false;
            for(int i = 0; i < 3 && !ok; ++i){
                for(int j = i + 1; j < 3 && !ok; ++j){
                    if(i == 1 && j == 2){
                        swap(paths[t[i]], paths.back());
                        swap(paths[t[j]], paths[sz - 2]);
                        ok = true;
                        break;
                    }
                    if(are_connected({paths[t[i]][0]}, {paths[t[j]][0]})){
                        swap(paths[t[i]], paths.back());
                        swap(paths[t[j]], paths[sz - 2]);
                        ok = true;
                        break;
                    }
                }
            }
        }
        else{
            if(!are_connected({paths[sz - 1][0]}, {paths[sz - 2][0]})){
                if(are_connected({paths[sz - 3][0]}, {paths[sz - 4][0]})){
                    swap(paths[sz - 1], paths[sz - 3]);
                    swap(paths[sz - 2], paths[sz - 4]);
                }
                else{
                    if(are_connected({paths[sz - 2][0]}, {paths[sz - 3][0]})){
                        swap(paths[sz - 3], paths[sz - 1]);
                    }
                    else{
                        swap(paths[sz - 3], paths[sz - 2]);

                        auto u = paths.back();
                        paths.pop_back();
                        auto v = paths.back();
                        paths.pop_back();

                        reverse(u.begin(), u.end());
                        for(int x: v)
                            u.push_back(x);

                        paths.push_back(u);
                        swap(paths.back(), paths[(int)paths.size() -  3]);
                    }
                }
            }
        }

        auto u = paths.back();
        paths.pop_back();
        auto v = paths.back();
        paths.pop_back();

        reverse(u.begin(), u.end());
        for(int x: v)
            u.push_back(x);
        paths.push_back(u);
    }

    if(paths.size() == 1)
        return paths[0];

    if(paths[1].size() > paths[0].size())
        swap(paths[0], paths[1]);

    bool conn = false;
    if(are_connected({paths[0][0]}, {paths[1][0]})){
        conn = true;
    }
    else if(are_connected({paths[0][0]}, {paths[1].back()})){
        reverse(paths[1].begin(), paths[1].end());
        conn = true;
    }
    else if(are_connected({paths[0].back()}, {paths[1][0]})){
        reverse(paths[0].begin(), paths[0].end());
        conn = true;
    }
    else if(are_connected({paths[0].back()}, {paths[1].back()})){
        reverse(paths[0].begin(), paths[0].end());
        reverse(paths[1].begin(), paths[1].end());
        conn = true;
    }

    if(conn){
        reverse(paths[0].begin(), paths[0].end());
        for(int x: paths[1])
            paths[0].push_back(x);
        return paths[0];
    }

    if(!are_connected(paths[0], paths[1]))
        return paths[0];

    auto get_prefix = [](const vector<int> &v, int idx){
        vector<int> ret;
        for(int i = 0; i <= idx; ++i)
            ret.push_back(v[i]);
        return ret;
    };

    int l1 = 0, r1 = (int)paths[0].size() - 1;
    while(l1 != r1){
        int mid = (l1 + r1) >> 1;
        if(are_connected(get_prefix(paths[0], mid), paths[1]))
            r1 = mid;
        else
            l1 = mid + 1;
    }

    int l2 = 0, r2 = (int)paths[1].size() - 1;
    while(l2 != r2){
        int mid = (l2 + r2) >> 1;
        if(are_connected({paths[0][l1]}, get_prefix(paths[1], mid)))
            r2 = mid;
        else
            l2 = mid + 1;
    }

    vector<int> ans;
    for(int i = l1 + 1; i < (int)paths[0].size(); ++i)
        ans.push_back(paths[0][i]);
    for(int i = 0; i <= l1; ++i)
        ans.push_back(paths[0][i]);

    for(int i = l2; i < (int)paths[1].size(); ++i)
        ans.push_back(paths[1][i]);
    for(int i = 0; i < l2; ++i)
        ans.push_back(paths[1][i]);

    return ans;
}

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