Submission #839901

#	Time	Username	Problem	Language	Result	Execution time	Memory
839901		emeraldblock	Longest Trip (IOI23_longesttrip)	C++17	60 / 100	197 ms	568 KiB

longesttrip

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

using namespace std;

std::vector<int> longest_trip(int N, int D)
{
    vector<int> path{0};
    vector<int> rest(N-1);
    iota(rest.begin(),rest.end(),1);
    while (rest.size()) {
        bool can = are_connected(path,rest);
        if (!can) {
            if (path.size() >= rest.size()) return path;
            return rest;
        }
        int lo = 0, hi = rest.size();
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            vector<int> cand;
            for (auto it = rest.begin()+lo; it != rest.begin()+mid; ++it) {
                cand.push_back(*it);
            }
            bool res = are_connected(path,cand);
            if (res) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        int nxt = rest[lo];
        rest.erase(rest.begin()+lo);
        if (are_connected({path.back()},{nxt})) {
            path.push_back(nxt);
        } else {
            lo = 0; hi = path.size();
            while (hi-lo > 1) {
                int mid = (lo+hi)/2;
                vector<int> cand;
                for (auto it = path.begin()+lo; it != path.begin()+mid; ++it) {
                    cand.push_back(*it);
                }
                bool res = are_connected(cand,{nxt});
                if (res) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            }
            if (lo == 0) {
                path.insert(path.begin(),nxt);
            } else {
                rotate(path.begin(),path.begin()+lo+1,path.end());
                path.push_back(nxt);
            }
        }
    }
    return path;
}

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