Drazil Likes Heap

Drazil likes heap very much. So he created a problem with heap:

There is a max heap with a height $h$ implemented on the array. The details of this heap are the following:

This heap contains exactly $2^h – 1$ distinct positive non-zero integers. All integers are distinct. These numbers are stored in the array $a$ indexed from $1$ to $2^h-1$. For any $1 < i < 2^h$, $a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor]$.

Now we want to reduce the height of this heap such that the height becomes $g$ with exactly $2^g-1$ numbers in heap. To reduce the height, we should perform the following action $2^h-2^g$ times:

Choose an index $i$, which contains an element and call the following function $f$ in index $i$:

Note that we suppose that if $a[i]=0$, then index $i$ don’t contain an element.

After all operations, the remaining $2^g-1$ element must be located in indices from $1$ to $2^g-1$. Now Drazil wonders what’s the minimum possible sum of the remaining $2^g-1$ elements. Please find this sum and find a sequence of the function calls to achieve this value.Input

The first line of the input contains an integer $t$ ($1 \leq t \leq 70\,000$): the number of test cases.

Each test case contain two lines. The first line contains two integers $h$ and $g$ ($1 \leq g < h \leq 20$). The second line contains $n = 2^h-1$ distinct positive integers $a[1], a[2], \ldots, a[n]$ ($1 \leq a[i] < 2^{20}$). For all $i$ from $2$ to $2^h – 1$, $a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor]$.

The total sum of $n$ is less than $2^{20}$.Output

For each test case, print two lines.

The first line should contain one integer denoting the minimum sum after reducing the height of heap to $g$. The second line should contain $2^h – 2^g$ integers $v_1, v_2, \ldots, v_{2^h-2^g}$. In $i$-th operation $f(v_i)$ should be called.Exampleinput

2
3 2
7 6 3 5 4 2 1
3 2
7 6 5 4 3 2 1

output

10
3 2 3 1
8
2 1 3 1

Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, m;
cin >> n >> m;
int pn = 1 << n;
    int pm = 1 << m;
    vector<int> a(pn);
for (int i = 1; i < pn; i++) {
      cin >> a[i];
}
vector<int> que(1, 1);
vector<int> seq;
vector<int> path;
for (int b = 0; b < (int) que.size(); b++) {
      while (true) {
        path.clear();
        int x = que[b];
        if (x >= pn || a[x] == 0) {
break;
}
path.push_back(x);
while (2 * x < pn) {
          int w = (a[2 * x] > a[2 * x + 1] ? 2 * x : 2 * x + 1);
x = w;
path.push_back(x);
}
int zeros = 0;
for (int i = (int) path.size() - 1; i >= 0; i--) {
if (a[path[i]] == 0) {
++zeros;
} else {
break;
}
}
if (zeros < n - m) {
          for (int i = 0; i < (int) path.size() - 1; i++) {
            a[path[i]] = a[path[i + 1]];
          }
          a[path.back()] = 0;
          seq.push_back(que[b]);
        } else {
          for (int i = 1; i < (int) path.size(); i++) {
            que.push_back((path[i] & 1) ? path[i] - 1 : path[i] + 1);
          }
          break;
        }
      }
    }
    long long ans = 0;
    for (int i = 1; i < pm; i++) {
      ans += a[i];
    }
    cout << ans << '\n';
    for (int i = 0; i < (int) seq.size(); i++) {
      if (i > 0) {
cout << " ";
      }
      cout << seq[i];
    }
    cout << '\n';
  }
  return 0;
}