Submission #841750

#	Time	Username	Problem	Language	Result	Execution time	Memory
841750		Lyestria	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	16 ms	1368 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()

mt19937_64 rnd(time(0));

using vi = vector<int>;

vi mrg(const vi&a, const vi&b) {
    vi c = a;
    for(int x : b) c.push_back(x);
    return c;
}

vector<int> longest_trip(int n, int d)
{
    deque<vi> pths;
    auto add_back =[&](const vi&v) {
        if(v.size()==1)pths.push_back(v);
        else pths.push_front(v);
    };
    for(int i=0;i<n;i++)add_back({i});
    shuffle(pths.begin(),pths.end(), rnd);
    while(pths.size()>2){
        auto v1 = pths.back();
        pths.pop_back();
        auto v2 = pths.back();
        pths.pop_back();
        if(are_connected({v1[0]}, {v2[0]})) {
            reverse(all(v1));
            auto v = mrg(v1,v2);
            add_back(v);
        }
        else {
            int no1 = 1, no2 = 1;
            if(v1.size()==1)no1=2;
            if(v2.size()==1)no2=2;
            while(no1&&no2&&pths.size()){
                auto v3 = pths.front();
                pths.pop_front();
                if(are_connected({v1[0]}, {v3[0]})){
                    reverse(all(v1));
                    v1 = mrg(v1,v3);
                    no1--;
                }
                else {
                    reverse(all(v2));
                    v2 = mrg(v2,v3);
                    no2--;
                }
            }
            add_back(v1);
            add_back(v2);
        }
    }


    if(pths.size()==1)return pths[0];
    auto v1 = pths[0], v2 = pths[1];

    if(are_connected({v1[0]},{v2[0]})){
        reverse(all(v2));
        return mrg(v2,v1);
    }
    if(are_connected({v1[0]},{v2.back()})){
        return mrg(v2,v1);
    }
    auto bsearch = [](vi v1, vi v2) {
        int l=0,r=v2.size()-1;
        while(l<r){
            // cerr << "bs " << l << " " << r << endl;
            int mid = (l+r)/2;
            vi sv {v2.begin()+l,v2.begin()+mid+1};
            if(are_connected(v1,sv)){
                r=mid;
            }
            else {
                l=mid+1;
            }
        }
        return l;
    };
    if(are_connected({v1[0]},v2)){
        int ind2 = bsearch({v1[0]},v2);
        // cerr << "R1 " << ind2 << endl;
        rotate(v2.begin(),v2.begin()+ind2,v2.end());
        reverse(all(v1));
        return mrg(v1,v2);
    }
    if(are_connected({v1.back()},{v2[0]})){
        return mrg(v1,v2);
    }
    swap(v1,v2);
    if(are_connected({v1[0]},v2)){
        int ind2 = bsearch({v1[0]},v2);
        rotate(v2.begin(),v2.begin()+ind2,v2.end());
        reverse(all(v1));
        return mrg(v1,v2);
    }
    if(are_connected(v1,v2)){
        int ind2 = bsearch(v1,v2);
        int ind1 = bsearch({v2[ind2]}, v1);
        // cerr << ind1 << " " << ind2 << endl;
        rotate(v1.begin(),v1.begin()+ind1,v1.end());
        // cerr << "rotate1" << endl;
        rotate(v2.begin(),v2.begin()+ind2,v2.end());
        reverse(all(v1));
        return mrg(v1,v2);
    }
    return v1.size() > v2.size() ? v1 : v2;
}

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