Submission #1077941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077941		PanosPask	Longest Trip (IOI23_longesttrip)	C++17	70 / 100	43 ms	676 KiB

longesttrip

#include "longesttrip.h"
#define pb push_back

using namespace std;

// Find the first posiion i such that v[i] is connected to i
int find_position(vector<int>& v, int i)
{
    int l = 0;
    int r = v.size();

    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (are_connected(vector<int>(v.begin(), v.begin() + mid), {i})) {
            r = mid;
        }
        else {
            l = mid;
        }
    }

    return l;
}

vector<int> longest_trip(int N, int D)
{
    vector<int> v1, v2;

    v1.push_back(0);

    for (int i = 1; i < N; i++) {
        if (are_connected(v1, {i})) {
            if (v2.size()) {
                if (are_connected(v2, {i})) {
                    int p1 = find_position(v1, i);
                    int p2 = find_position(v2, i);

                    v1.pb(v1[p1]);
                    v1.erase(v1.begin() + p1);
                    v1.pb(i);
                    v1.pb(v2[p2]);
                    v2.erase(v2.begin() + p2);
                    v1.insert(v1.end(), v2.begin(), v2.end());

                    v2.clear();
                }
                else {
                    v1.pb(i);
                }
            }
            else {
                if (are_connected({v1.back()}, {i})) {
                    v1.pb(i);
                }
                else {
                    int p = find_position(v1, i);
                    v1.insert(v1.end(), v1.begin(), v1.begin() + p);
                    v1.erase(v1.begin(), v1.begin() + p);
                    v1.insert(v1.begin(), i);
                }
            }
        }
        else {
            v2.pb(i);
        }
    }

    if (v1.size() > v2.size()) {
        return v1;
    }
    else {
        return v2;
    }
}

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