Вам дана реализация декартова дерева. Ошибок тут нет, не волнуйтесь. Есть одна особенность: вместо \textbf{y}-ков в операции \textbf{Merge} используется \textbf{rnd.next(2)} (функция возвращает случайное число от \textbf{0} до \textbf{1}). Утверждается, что построенное таким образом дерево может иметь слишком большую глубину. Ваша задача --- найти последовательность из не более чем \textbf{3000} операций, создающую дерево глубины не менее \textbf{1000} (дерево из одной вершины имеет глубину \textbf{1}). 1 typede f struct tree * ptree; 2 struct tree \{ ptree l, r; i n t x; \}; 3 ptree root, a, b, c; 4 5 // 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( i n t 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( i n t x ) \{ 24 Split(root, a, b, x); 25 Split(b, b, c, x + 1); 26 Merge(root, a, c); 27 \} \InputFile Вам предоставлен абсолютно пустой файл. Дерево изначально также пусто. \InputFile Последовательность операций вида \textbf{ADD x} и \textbf{DEL x}. \textbf{ADD x} вызывает функцию \textbf{Add(x)} (см. реализацию) \textbf{DEL x} вызывает функцию \textbf{Del(x)} (см. реализацию) \Note В чекере используется \textbf{Random} не зависящий от времени. Т.е. одинаковые решения всегда получают одинаковый результат. Если вы получили \textbf{PE}, ваш вывод не является корректной последовательностью из не более чем \textbf{3000}операций. Если вы получили \textbf{WA}, последовательность операций корректна, а получившееся дерево имеет глубину меньше \textbf{1000}.