oj.uz

Submission #647695

# Submission time Handle Problem Language Result Execution time Memory
647695 2022-10-03T16:15:47 Z borgar02 Zalmoxis (BOI18_zalmoxis) C++17
50 / 100
 579 ms 73092 KB 
#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

zalmoxis.cpp: In constructor 'node::node(int)':
zalmoxis.cpp:8:67: warning: list-initializer for non-class type must not be parenthesized
    8 |     node(int h) : ch({NULL, NULL}), marked(false), vis(false), h(h) {}
      |                                                                   ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from zalmoxis.cpp:1:
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:73:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |     assert(res.size() == n + ck);
      |            ~~~~~~~~~~~^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 72956 KB Output is correct
2 Correct 579 ms 72944 KB Output is correct
3 Correct 524 ms 72980 KB Output is correct
4 Correct 512 ms 72868 KB Output is correct
5 Correct 533 ms 72900 KB Output is correct
6 Correct 534 ms 72872 KB Output is correct

Subtask #2
20.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 73040 KB Output is correct
2 Incorrect 490 ms 72872 KB doesn't contain S as a subsequence
3 Incorrect 480 ms 72936 KB doesn't contain S as a subsequence
4 Incorrect 486 ms 73056 KB doesn't contain S as a subsequence
5 Incorrect 503 ms 73012 KB doesn't contain S as a subsequence
6 Incorrect 548 ms 72968 KB doesn't contain S as a subsequence
7 Correct 498 ms 73092 KB Output is correct
8 Correct 496 ms 72908 KB Output is correct
9 Incorrect 445 ms 72168 KB doesn't contain S as a subsequence
10 Incorrect 273 ms 70140 KB doesn't contain S as a subsequence
11 Incorrect 359 ms 70976 KB doesn't contain S as a subsequence
12 Incorrect 174 ms 68948 KB doesn't contain S as a subsequence
13 Incorrect 178 ms 68892 KB doesn't contain S as a subsequence
14 Correct 172 ms 68944 KB Output is correct