Submission #508402

#	Time	Username	Problem	Language	Result	Execution time	Memory
508402		KoD	Volontiranje (COCI21_volontiranje)	C++17	110 / 110	400 ms	151124 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

constexpr int INF = std::numeric_limits<int>::max() / 2;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> P(N);
    for (auto& x : P) {
        std::cin >> x;
        x -= 1;
    }
    vector<int> left(N);
    {
        vector<int> dp(N + 1, INF);
        dp[0] = -INF;
        for (int i = 0; i < N; ++i) {
            auto itr = std::lower_bound(dp.begin(), dp.end(), P[i]);
            left[i] = itr - dp.begin();
            *itr = P[i];
        }
    }
    vector<int> right(N);
    {
        vector<int> dp(N + 1, INF);
        dp[0] = -INF;
        for (int i = N - 1; i >= 0; --i) {
            auto itr = std::lower_bound(dp.begin(), dp.end(), -P[i]);
            right[i] = itr - dp.begin();
            *itr = -P[i];
        }
    }
    int max = 0;
    for (int i = 0; i < N; ++i) {
        max = std::max(max, left[i] + right[i] - 1);
    }
    vector<vector<int>> list(max);
    for (int i = 0; i < N; ++i) {
        if (left[i] + right[i] - 1 == max) {
            list[left[i] - 1].push_back(i);
        }
    }
    vector<vector<int>> ans;
    vector<int> idx(max);
    vector<char> used(N);
    while (idx[0] < (int)list[0].size()) {
        vector<int> path;
        RecLambda([&](auto&& dfs, const int k, const int i) -> bool {
            const int u = list[k][i];
            path.push_back(u);
            if (k + 1 == max) {
                ans.push_back(path);
                return true;
            }
            while (idx[k + 1] < (int)list[k + 1].size()) {
                const int v = list[k + 1][idx[k + 1]];
                if (u > v or used[v]) {
                    idx[k + 1] += 1;
                    continue;
                }
                if (P[u] > P[v]) {
                    break;
                }
                if (dfs(k + 1, idx[k + 1])) {
                    return true;
                }
                idx[k + 1] += 1;
            }
            path.pop_back();
            return false;
        })(0, idx[0]++);
        for (const int u : path) {
            used[u] = true;
        }
    }
    std::cout << ans.size() << ' ' << max << '\n';
    for (const auto& v : ans) {
        for (int i = 0; i < max; ++i) {
            std::cout << v[i] + 1 << " \n"[i + 1 == max];
        }
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60