oj.uz

Submission #530476

# Submission time Handle Problem Language Result Execution time Memory
530476 2022-02-25T13:25:32 Z KoD Swap (BOI16_swap) C++17
68 / 100
 1000 ms 191696 KB 
#include <bits/extc++.h>

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

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

vector<int> merge(const int top, const vector<int>& l, const vector<int>& r) {
    const int n = l.size(), m = r.size();
    vector<int> ret;
    ret.reserve(1 + n + m);
    ret.push_back(top);
    int i = 0, j = 1;
    while (i < n or i < m) {
        for (int k = i; k < i + j and k < n; ++k) {
            ret.push_back(l[k]);
        }
        for (int k = i; k < i + j and k < m; ++k) {
            ret.push_back(r[k]);
        }
        i += j;
        j <<= 1;
    }
    return ret;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;
    vector<int> X(N);
    for (auto& x : X) {
        std::cin >> x;
    }

    std::unordered_map<long long, vector<int>> dp;
    const auto code = [&](const int root, const int top) {
        return ((long long)root << 18) + top;
    };

    const auto ans = rec_lambda([&](auto&& dfs, const int root, const int top) -> vector<int> {
        auto& ret = dp[code(root, top)];
        if (!ret.empty()) {
            return ret;
        }
        const int lch = 2 * root + 1, rch = 2 * root + 2;
        if (lch >= N) {
            return ret = {top};
        }
        if (rch >= N) {
            if (top < X[lch]) {
                return ret = {top, X[lch]};
            } else {
                return ret = {X[lch], top};
            }
        }
        int a = top, b = X[lch], c = X[rch];
        if (a < b and a < c) {
            return ret = merge(a, dfs(lch, b), dfs(rch, c));
        }
        if (b < a and b < c) {
            return ret = merge(b, dfs(lch, a), dfs(rch, c));
        }
        return ret = std::min(merge(c, dfs(lch, a), dfs(rch, b)), merge(c, dfs(lch, b), dfs(rch, a)));
    })(0, X[0]);

    for (int i = 0; i < N; ++i) {
        std::cout << ans[i] << " \n"[i + 1 == N];
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 3 ms 1100 KB Output is correct
15 Correct 3 ms 1100 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 3 ms 1100 KB Output is correct
15 Correct 3 ms 1100 KB Output is correct
16 Correct 74 ms 16484 KB Output is correct
17 Correct 74 ms 16384 KB Output is correct
18 Correct 86 ms 16880 KB Output is correct
19 Correct 649 ms 90812 KB Output is correct
20 Correct 595 ms 80492 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 3 ms 1100 KB Output is correct
15 Correct 3 ms 1100 KB Output is correct
16 Correct 74 ms 16484 KB Output is correct
17 Correct 74 ms 16384 KB Output is correct
18 Correct 86 ms 16880 KB Output is correct
19 Correct 649 ms 90812 KB Output is correct
20 Correct 595 ms 80492 KB Output is correct
21 Correct 446 ms 70580 KB Output is correct
22 Correct 447 ms 70312 KB Output is correct
23 Correct 449 ms 71472 KB Output is correct
24 Execution timed out 1103 ms 191696 KB Time limit exceeded
25 Halted 0 ms 0 KB -