Submission #1242502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242502		someone	Longest Trip (IOI23_longesttrip)	C++20	85 / 100	5 ms	424 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

int dicho(vector<int> a, vector<int> b) {
    if((int)a.size() == 1) return a[0];
    vector<int> cut[2];
    int cnt = 0;
    for(int i : a) {
        cnt++;
        cut[cnt % 2].push_back(i);
    }
    if(are_connected(cut[1], b)) return dicho(cut[1], b);
    return dicho(cut[0], b);
}

bool seeded = false;

vector<int> longest_trip(int N, int D) {
    vector<int> a, b;
    if(!seeded) srand(N ^ ((D * 165) + 42));
    seeded = true;
    
    vector<int> perm(N);
    for(int i = 0; i < N; i++)
        perm[i] = i;
    random_shuffle(perm.begin(), perm.end());
    a.push_back(perm[0]);
    for(int i = 1; i < N; i++) {
        if(b.empty()) {
            if(are_connected({a.back()}, {perm[i]}))
                a.push_back(perm[i]);
            else
                b.push_back(perm[i]);
        } else {
            if(rand() % 2 == 0) swap(a, b);
            if(are_connected({a.back()}, {perm[i]})) {
                a.push_back(perm[i]);
                if(are_connected({a.back()}, {b.back()})) {
                    while(!b.empty()) {
                        a.push_back(b.back());
                        b.pop_back();
                    }
                }
            } else {
                b.push_back(perm[i]);
            }
        }
    }

    if(b.empty()) return a;

    if((int)a.size() == 1 || are_connected({a[0]}, {a.back()})) {
        if((int)b.size() == 1 || are_connected({b[0]}, {b.back()})) {
            if(are_connected(a, b)) {
                int x = dicho(a, b);
                int y = dicho(b, {x});
                deque<int> A, B;
                for(int i : a) A.push_back(i);
                for(int i : b) B.push_back(i);
                while(A.back() != x) {
                    A.push_back(A[0]);
                    A.pop_front();
                }
                while(B[0] != y) {
                    B.push_back(B[0]);
                    B.pop_front();
                }
                vector<int> ans;
                for(int i : A) ans.push_back(i);
                for(int i : B) ans.push_back(i);
                return ans;
            } else {
                if(a.size() < b.size()) swap(a, b);
                return a;
            }
        } else {
            swap(a, b);
        }
    }
    if(are_connected({a[0]}, {b.back()})) {
        for(int i : a) b.push_back(i);
        return b;
    } else {
        while(!b.empty()) {
            a.push_back(b.back());
            b.pop_back();
        }
        return a;
    }
}

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