QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #803725 | #9806. Growing Tree | Tobo | WA | 3ms | 4104kb | C++20 | 2.1kb | 2024-12-07 18:11:07 | 2024-12-07 18:11:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128_t;
bool Memory_begin;
bool Memory_end;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cerr << (&Memory_end - &Memory_begin) / 1048576.0 << "MB" << '\n';
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> a(1 << (n + 1));
for (int i = 2; i < a.size(); i++)
cin >> a[i];
for (int i = 2; i < (1 << n); i++)
a[i * 2] += a[i], a[i * 2 + 1] += a[i];
int ans = n + 1;
vector<vector<int>> S(1 << (n + 1));
for (int i = (1 << n); i < a.size(); i++)
S[i] = {a[i]};
auto dfs = [&](auto &dfs, int cur, int used) -> void
{
if (!cur)
{
ans = min(ans, used);
return;
}
auto &lft = S[cur << 1], &rht = S[cur << 1 | 1];
bool same = false;
for (int i = 0, j = 0; i < lft.size() or j < rht.size();)
{
if (i == lft.size())
S[cur].push_back(rht[j++]);
else if (j == rht.size())
S[cur].push_back(lft[i++]);
else
{
if (lft[i] == rht[j])
same = true;
if (lft[i] <= rht[j])
S[cur].push_back(lft[i++]);
else
S[cur].push_back(rht[j++]);
}
}
if (!same)
return dfs(dfs, cur - 1, used);
used++;
int dep = 32 - __builtin_clz(cur);
if (used > n - dep + 1)
return;
S[cur] = lft;
dfs(dfs, cur - 1, used);
S[cur] = rht;
dfs(dfs, cur - 1, used);
};
dfs(dfs, (1 << n) - 1, 0);
if (ans == n + 1)
ans = -1;
cout << ans << '\n';
}
}
/*
3
2
1 2 4 3 2 1
2
1 2 3 3 2 1
2
1 2 3 3 1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3936kb
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: 3ms
memory: 4104kb
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:
2 0 -1 2 0 1 -1 0 0 3 0 0 0 1 2 1 0 2 0 1 0 -1 0 -1 0 0 -1 -1 -1 -1 -1 3 -1 0 3 2 7 -1 -1 -1 1 2 4 0 0 2 7 1 6 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 7 0 0 0 0 1 0 -1 3 3
result:
wrong answer 32nd numbers differ - expected: '4', found: '3'