# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
647695 | borgar02 | Zalmoxis (BOI18_zalmoxis) | C++17 | 579 ms | 73092 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct node {
node *ch[2];
bool marked, vis;
int h;
node(int h) : ch({NULL, NULL}), marked(false), vis(false), h(h) {}
node *go_to(int s) { if(ch[s] == NULL) { ch[!s] = new node(h - 1); return ch[s] = new node(h - 1); } return ch[s]; }
bool cansplit() { return !ch[0] && !ch[1] && h; }
};
node *root = new node(30);
bool add(int x, int curr = 30, node *t = root)
{
// cout << curr << "\n";
if(t -> vis) return false;
if(curr == x && !(t -> ch[0])) { return t -> vis = t -> marked = true;}
else if(curr == x) return false;
// cout << "Going left\n";
bool ok;
if(!(ok = add(x, curr - 1, t -> go_to(0)))) {
// cout << "Going right\n";
ok = add(x, curr - 1, t -> go_to(1));
}
if(!ok) t -> vis = true;
return ok;
}
const int N = 1e6 + 5;
int a[N];
int k;
int cnt;
void count_leaves(node *t = root)
{
if(t -> ch[0]) {
count_leaves(t -> ch[0]);
count_leaves(t -> ch[1]);
} else if(!t -> marked) cnt++;
}
void dfs(node *t = root)
{
if(!t -> ch[0] && !t -> marked && k && t -> cansplit()) {
k--;
t -> go_to(0);
}
if(t -> ch[0]) {
dfs(t -> ch[0]);
dfs(t -> ch[1]);
}
}
vector <int> res;
void dfs2(node *t = root)
{
if(t -> ch[0]) {
dfs2(t -> ch[0]);
dfs2(t -> ch[1]);
} else res.push_back(t -> h);
}
int main()
{
root -> go_to(0);
int n;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
assert(add(a[i]));
}
count_leaves();
int ck = k;
k -= cnt;
dfs();
dfs2();
assert(res.size() == n + ck);
for(int x : res)
cout << x << " ";
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |