oj.uz

Submission #508401

# Submission time Handle Problem Language Result Execution time Memory
508401 2022-01-13T10:22:18 Z KoD Volontiranje (COCI21_volontiranje) C++17
0 / 110
 0 ms 316 KB 
#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() << '\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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 316 KB length of the longest increasing subsequence doesn't match
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 316 KB length of the longest increasing subsequence doesn't match
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 316 KB length of the longest increasing subsequence doesn't match
2 Halted 0 ms 0 KB -