Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
169319958 Дорешивание:
chengchunhao
1329C - 20 C++17 (GCC 9-64) Полное решение 1372 мс 137380 КБ 2022-08-22 13:10:50 2022-08-22 13:10:58
→ Исходный код
#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;
}
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования