Submission #1144237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144237		Math4Life2020	Longest Trip (IOI23_longesttrip)	C++20	0 / 100	0 ms	408 KiB

longesttrip

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

// bool are_connected(vector<int> v0, vector<int> v1) {
//     return 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 (are_connected(ccur,(vector<int>){cnum[0]})) {
        vector<ll> vfin = ccur;
        for (ll y: cnum) {
            vfin.push_back(y);
        }
        return vfin;
    }
    if (!are_connected(cnum,ccur)) {
        if (cnum.size()<ccur.size()) {
            return ccur;
        } else {
            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 it = imin;
    vector<ll> vfin = ccur;
    for (ll i=0;i<M;i++) {
        vfin.push_back(cnum[(i+it)%M]);
    }
    return vfin;
}

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