?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
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; }
?
?
?
?