QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#795842 | #9806. Growing Tree | thinking (Fedor Romashov, Alexey Mikhnenko, Gimran Abdullin)# | WA | 6ms | 3716kb | C++20 | 2.7kb | 2024-12-01 02:24:26 | 2024-12-01 02:24:26 |
Judging History
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'