General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
169319958 Practice:
chengchunhao
1329C - 20 C++17 (GCC 9-64) Accepted 1372 ms 137380 KB 2022-08-22 13:10:50 2022-08-22 13:10:58
→ Source
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N = (1 << 20) + 5;
int h, g;
int a[N], pos[N], val[N];
ll ans;
bool flag[N];
vector<int> vec[N];

void dfs(int u) {
    if ((u << 1) >= (1 << h)) {
        vec[u].pb(a[u]);
        return;
    }
    dfs(u << 1);
    dfs(u << 1 | 1);
    // merge
    {
        int i = 0, j = 0;
        while (i < vec[u << 1].size() && j < vec[u << 1 | 1].size()) {
            if (vec[u << 1][i] < vec[u << 1 | 1][j])
                vec[u].pb(vec[u << 1][i++]);
            else
                vec[u].pb(vec[u << 1 | 1][j++]);
        }
        while (i < vec[u << 1].size())
            vec[u].pb(vec[u << 1][i++]);
        while (j < vec[u << 1 | 1].size())
            vec[u].pb(vec[u << 1 | 1][j++]);
        vec[u].pb(a[u]);
        vec[u << 1].clear(), vec[u << 1 | 1].clear();   
    }
    if (u <= (1 << g) - 1) {
        int s = max(val[u << 1], val[u << 1 | 1]);
        val[u] = *upper_bound(vec[u].begin(), vec[u].end(), s);
        flag[pos[val[u]]] = true;
        ans += val[u];
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> h >> g;

        ans = 0;
        for (int i = 1; i < 1 << h; i++) {
            val[i] = 0;
            flag[i] = false;
        }
        vec[1].clear();

        for (int i = 1; i < 1 << h; i++) {
            scanf("%d", &a[i]);
            pos[a[i]] = i;
        }
        dfs(1);
        printf("%lld\n", ans);
        for (int i = (1 << h) - 1; i >= 1; i--) 
            if (!flag[i])
                printf("%d ", i);
        printf("\n");
    }
    return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details