QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#795842#9806. Growing Treeucup-team4435#WA 6ms3716kbC++202.7kb2024-12-01 02:24:262024-12-01 02:24:26

Judging History

This is the latest submission verdict.

  • [2024-12-01 02:24:26]
  • Judged
  • Verdict: WA
  • Time: 6ms
  • Memory: 3716kb
  • [2024-12-01 02:24:26]
  • Submitted

answer

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

using ll = long long;
using ld = long double;

#define all(a) begin(a), end(a)
#define len(a) int((a).size())

template<typename Fun>
struct y_combinator {
    const Fun fun;

    explicit y_combinator(const Fun&& fun) : fun(std::forward<const Fun>(fun)) {}

    template<typename... Args>
    auto operator()(Args&&... args) const {
        return fun(std::ref(*this), std::forward<Args>(args)...);
    }
};

void solve(int /* test_num */) {
    int n;
    cin >> n;
    const int N = (1 << (n + 1));
    vector<int> a(N);
    for (int i = 2; i < N; i++) {
        cin >> a[i];
    }

    auto [dp, st] = y_combinator([&](auto solve, int v) -> pair<vector<bool>, set<int>> {
        int left = 2 * v, right = 2 * v + 1;
        if (left >= N) {
            return {vector<bool>(1, true), set<int>{a[v]}};
        }

        auto [ldp, lst] = solve(left);
        auto [rdp, rst] = solve(right);

        bool intersects = false;
        set<int> nst;
        for (auto x : lst) {
            if (rst.count(x)) {
                intersects = true;
            }
            nst.insert(x + a[v]);
        }
        for (auto x : rst) {
            nst.insert(x + a[v]);
        }

        assert(len(ldp) == len(rdp));
        const int M = len(ldp);
        vector<bool> ndp(2 * M);

        int lg = 0;
        while (M != (1 << lg)) {
            lg++;
        }

        for (int lmask = 0; lmask < M; lmask++) {
            for (int rmask = 0; rmask < M; rmask++) {
                if (!ldp[lmask] || !rdp[rmask]) {
                    continue;
                }

                int nmask = 0, carry = 0;
                for (int i = 0; i < lg; i++) {
                    carry += (lmask >> i & 1) + (rmask >> i & 1);
                    if (carry >= 1) {
                        carry--;
                        nmask ^= (1 << i);
                    }
                }

                if (carry > 0) {
                    continue;
                }

                nmask *= 2;
                if (intersects) {
                    nmask ^= 1;
                }
                ndp[nmask] = true;
            }
        }

        return {ndp, nst};
    })(1);

    int ans = 1e9;
    for (int mask = 0; mask < len(dp); mask++) {
        if (dp[mask]) {
            ans = min(ans, __builtin_popcount(mask));
        }
    }
    if (ans > 1e8) {
        ans = -1;
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    for (int test_num = 1; test_num <= tests; test_num++) {
        solve(test_num);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

3
2
1 2 4 3 2 1
2
1 2 3 3 2 1
2
1 2 3 3 1 1

output:

1
2
-1

result:

ok 3 number(s): "1 2 -1"

Test #2:

score: -100
Wrong Answer
time: 6ms
memory: 3716kb

input:

94
5
44 65 38 61 64 94 71 53 65 10 24 36 98 74 11 4 5 46 72 34 9 24 37 32 76 29 48 88 17 14 36 4 22 6 71 53 24 61 89 79 39 57 99 61 27 85 99 46 81 75 90 25 16 13 1 87 55 81 56 78 67 2
3
83 3 74 14 45 17 22 41 62 74 25 1 56 22
7
21 73 83 99 3 91 16 53 8 10 49 29 54 81 45 10 12 68 32 9 30 11 99 85 73 ...

output:

3
0
-1
2
0
1
-1
0
0
4
0
0
0
1
2
1
0
2
0
2
0
-1
0
-1
0
0
-1
-1
-1
-1
-1
5
-1
0
4
2
-1
-1
-1
-1
2
2
6
0
0
3
-1
1
7
0
-1
2
-1
0
0
0
-1
1
-1
-1
0
0
1
1
-1
0
1
2
0
-1
0
0
1
1
-1
0
-1
0
0
0
-1
3
-1
1
-1
0
0
0
0
1
0
-1
4
4

result:

wrong answer 1st numbers differ - expected: '2', found: '3'