Submission #1056441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056441		Triseedot	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	367 ms	748 KiB

longesttrip

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

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif

using ll = long long;
#define all(v) v.begin(), v.end()
#define len(v) int(v.size())

const ll INF = 1e18;

bool are_connected(vector<int> A, vector<int> B);

vector<int> longest_trip(int N, int D) {
    if (D == 3) {
        vector<int> res(N);
        iota(all(res), 0);
        return res;
    }
    set<vector<int>> p;
    for (int i = 0; i < N; i++) p.insert({i});
    while (len(p) > 2) {
        auto v = *p.begin(), u = *next(p.begin()), w = *next(next(p.begin()));
        vector<int> x;
        if (are_connected({v[0]}, {u[0]})) {
            x = v;
            reverse(all(x));
            for (int el : u) x.push_back(el);
            p.erase(v);
            p.erase(u);
        }
        else if (are_connected({v[0]}, {w[0]})) {
            x = v;
            reverse(all(x));
            for (int el : w) x.push_back(el);
            p.erase(v);
            p.erase(w);
        }
        else {
            x = u;
            reverse(all(x));
            for (int el : w) x.push_back(el);
            p.erase(u);
            p.erase(w);
        }
        p.insert(x);
    }
    vector a = *p.begin(), b = *prev(p.end());
    if (len(a) < len(b)) swap(a, b);
    int best_i = -1, best_j = -1, best = len(a);
    for (int i = 0; i < len(a); i++) {
        for (int j = 0; j < len(b); j++) {
            int v = a[i], u = b[j];
            if (are_connected({v}, {u})) {
                int l = max(i + 1, len(a) - i) + max(j + 1, len(b) - j);
                if (l > best) {
                    best_i = i;
                    best_j = j;
                    best = l;
                }
            }
        }
    }
    if (best_i == -1) {
        return a;
    }
    else {
        vector<int> x;
        if (best_i + 1 > len(a) - best_i) {
            for (int i = 0; i <= best_i; i++) {
                x.push_back(a[i]);
            }
        }
        else {
            for (int i = len(a) - 1; i >= best_i; i--) {
                x.push_back(a[i]);
            }
        }
        if (best_j + 1 > len(b) - best_j) {
            for (int j = best_j; j >= 0; j--) {
                x.push_back(b[j]);
            }
        }
        else {
            for (int j = best_j; j < len(b); j++) {
                x.push_back(b[j]);
            }
        }
        return x;
    }
}

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