Submission #1144252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144252		Math4Life2020	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	5 ms	432 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>; using vi = vector<ll>;



void stest(vector<ll> v0) {
    for (ll i=0;i<(v0.size()-1);i++) {
        assert(are_connected((vi){v0[i]},(vi){v0[i+1]}));
    }
}

vector<ll> longest_trip(int N, int D) {
    vector<ll> cnum,ccur; //current vector, current "stack"
    queue<ll> rnum; //remaining nums
    ll x0 = 0;
    cnum.push_back(0);
    for (ll i=1;i<N;i++) {
        rnum.push(i);
    }
    while (!rnum.empty()) {
        x0 = cnum[cnum.size()-1];
        ll x1 = rnum.front(); rnum.pop();
        ccur.push_back(x1);
        if (are_connected((vector<int>){x0},(vector<int>{x1}))) {
            sort(ccur.rbegin(),ccur.rend());
            for (ll y: ccur) {
                cnum.push_back(y);
            }
            ccur.clear();
            x0 = cnum[cnum.size()-1];
        }
    }
    if (ccur.size()==0) {
        stest(cnum);
        return cnum;
    }
    if (are_connected(ccur,(vector<int>){cnum[0]})) {
        vector<ll> vfin = ccur;
        for (ll y: cnum) {
            vfin.push_back(y);
        }
        stest(vfin);
        return vfin;
    }
    if (!are_connected(cnum,ccur)) {
        if (cnum.size()<ccur.size()) {
            //stest(ccur);
            return ccur;
        } else {
            //stest(cnum);
            return cnum;
        }
    }
    ll M = cnum.size();
    ll imin = 0; ll imax = M-1;
    while (imin<imax) {
        ll it = (imin+imax)/2;
        vector<ll> vtest;
        for (ll j=imin;j<=it;j++) {
            vtest.push_back(cnum[j]);
        }
        if (are_connected(vtest,ccur)) {
            imax = it;
        } else {
            imin = it+1;
        }
    }
    ll K = ccur.size();
    ll jmin = 0; ll jmax = K-1;
    while (jmin<jmax) {
        ll jt = (jmin+jmax)/2;
        vector<ll> vtest;
        for (ll j=jmin;j<=jt;j++) {
            vtest.push_back(ccur[j]);
        }
        if (are_connected(vtest,(vector<ll>){cnum[imin]})) {
            jmax = jt;
        } else {
            jmin = jt+1;
        }
    }
    assert(are_connected((vector<ll>){cnum[imin]},(vector<ll>){ccur[jmin]}));
    vector<ll> vfin;
    for (ll i=1;i<=K;i++) {
        vfin.push_back(ccur[(i+jmin)%K]);
    }
    for (ll i=0;i<M;i++) {
        vfin.push_back(cnum[(i+imin)%M]);
    }
    //stest(vfin);
    return vfin;
}

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