시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 21 | 7 | 7 | 63.636% |
Professor Anna van Lier is preparing to give a lecture on balanced binary search trees. Recall that these are binary trees with two properties:
Anna got a picture of such a tree from a colleague. This tree has n nodes with the values 1 to n. However, it turns out to be too big to fit on her slides so she would like to make it smaller. In particular, she would like to erase some nodes from the tree such that it has exactly k remaining nodes. Whenever she erases a node, she also erases the subtrees of that node. Of course, the resulting tree must still be a balanced binary search tree.
For pedagogical purposes, Anna would like the node values in her final tree to be small. Therefore, she wants the list of the k remaining node values to be the lexicographically smallest possible. For example she would prefer a tree containing values 2, 5, 9 over a tree containing values 2, 6, 7.
As Anna is far too busy doing more important things, the task of finding which nodes to erase falls upon one of her teaching assistants, i.e., you.
Figure B.1: Illustration of Sample Input 2 and its solution.
The input consists of:
It is guaranteed that the given tree is a balanced binary search tree.
Output a single line with a binary string of length n. The ith character should be ‘1’ if the node with value i should be kept, and ‘0’ if it should be erased.
3 1 2 -1 2
010
8 5 3 1 -1 5 7 5 3 7
11101010
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2019 B번