Submission #1115557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115557		Gray	Longest Trip (IOI23_longesttrip)	C++17	5 / 100	39 ms	608 KiB

longesttrip

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

using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
ll n, d;
pair<ll, vector<ll>> mx;

vector<int> longest_trip(int N, int D)
{
    n=N; d=D;
    vector<int> a = {0}, b;
    for (int i=1; i<N; i++){
        if (are_connected({a.back()}, vector<int>{i})){
            a.push_back(i);
        }else{
            b.push_back(i);
        }
    }
    if (a.empty() or b.empty()){
        return a.empty()?b:a;
    }else if (are_connected(a, b)){
        ll l=0, r=a.size();
        while (l<r){
            vector<int> test;
            ll mid = (l+r)/2;
            for (ll i=l; i<=mid; i++){
                test.push_back(a[i]);
            }
            if (are_connected(test, b)){
                r=mid;
            }else l=mid+1;
        }
        int conA = a[r];
        l=0; r=b.size();
        while (l<r){
            vector<int> test;
            ll mid = (l+r)/2;
            for (ll i=l; i<=mid; i++){
                test.push_back(b[i]);
            }
            if (are_connected(test, {conA})){
                r=mid;
            }else l=mid+1;
        }
        int conB = b[r];

        vector<int> res;
        for (auto ch:a){
            if (ch==conA) continue;
            res.push_back(ch);
        }
        res.push_back(conA);
        res.push_back(conB);
        for (auto ch:b){
            if (ch==conB) continue;
            res.push_back(ch);
        }
        return res;
    }else{
        if (a.size()>b.size()) return a;
        else return b;
    }
}

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