Antitest#2963
You are given an implementation of a Cartesian tree. There's nothing wrong with the implementation itself, so no need to worry. However, there's a unique aspect: instead of using -values in the operation, the function is used, which returns a random number between and . It is suggested that a tree built this way might end up with excessive depth. Your task is to devise a sequence of no more than operations that results in a tree with a depth of at least (note that a tree with a single vertex has a depth of ).
1 typedef struct tree *ptree;
2 struct tree { ptree l, r; int x; };
3 ptree root, a, b, c;
// comment: l = {y < x}, r = {y >= x}
6 void Split(ptree t, ptree &l, ptree &r, int x) {
7 if (t == 0) l = r = 0;
8 else if (t->x >= x) Split(t->l, l, t->l, x), r = t;
9 else Split(t->r, t->r, r, x), l = t;
10 }
11 void Merge(ptree &t, ptree l, ptree r) {
12 if (l == 0) t = r;
13 else if (r == 0) t = l;
14 else if (rnd.next(2)) t = l, Merge(t->r, t->r, r);
15 else t = r, Merge(t->l, l, t->l);
16 }
17 void Add(int x) {
18 b = new tree(x);
19 Split(root, a, c, x);
20 Merge(a, a, b);
21 Merge(root, a, c);
22 }
23 void Del(int x) {
24 Split(root, a, b, x);
25 Split(b, b, c, x + 1);
26 Merge(root, a, c);
27 }You start with an entirely empty file. The tree is initially empty as well.
A sequence of operations in the form of and .
- invokes the function (refer to the implementation). - invokes the function (refer to the implementation).
مثال 1
The checker uses a function that is independent of time, meaning identical solutions will always yield the same result. If you receive a (Presentation Error), your output is not a valid sequence of no more than operations. If you receive a (Wrong Answer), the sequence of operations is valid, but the resulting tree's depth is less than .