Submission #1115640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115640		Gray	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	42 ms	604 KiB

longesttrip

#include "longesttrip.h"
#include <algorithm>
#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 = {1};
    bool lost=0;
    for (int i=2; i<N; i++){
        if (are_connected({a.back()}, {i})){
            a.push_back(i);
        }else if (lost or are_connected({b.back()}, {i})){
            b.push_back(i);
        }else{
            if (lost) assert(false);
            lost=1;
            assert(are_connected({a.back()}, {b.back()}));
            while (!b.empty()){
                a.push_back(b.back());
                b.pop_back();
            }
            b.push_back(i);
        }
    }
    // for (auto ch:a) cout << ch << " ";
    // cout << ln;
    // for (auto ch:b) cout << ch << " ";
    // cout << ln;
    if (a.empty() or b.empty()){
        return a.empty()?b:a;
    }else if (are_connected({a[0]}, {b[0]})){
        reverse(a.begin(), a.end());
        for (auto ch:b) a.push_back(ch);
        return a;
    }else if (are_connected({a[0]}, {b.back()})){
        for (auto ch:a) b.push_back(ch);
        return b;
    }else if (are_connected({a.back()}, {b[0]})){
        for (auto ch:b) a.push_back(ch);
        return a;
    }else if (are_connected({a.back()}, {b.back()})){
        reverse(b.begin(), b.end());
        for (auto ch:b) a.push_back(ch);
        return a;
    }else if (are_connected(a, b)){
        // cout << "Happening" << endl;
        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 = 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 = r;

        vector<int> res;
        for (int i=conA+1; i<(int)a.size(); i++){
            res.push_back(a[i]);
        }
        for (int i=0; i<=conA; i++){
            res.push_back(a[i]);
        }
        // cout << a[conA] << " " << b[conB] << endl;
        for (int i=conB; i<(int)b.size(); i++) res.push_back(b[i]);
        for (int i=0; i<conB; i++) res.push_back(b[i]);
        return res;
    }else{
        if (a.size()>b.size()) return a;
        else return b;
    }
}

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