Problems
Антитест
Антитест
Вам дана реализация декартова дерева. Ошибок тут нет, не волнуйтесь. Есть одна особенность: вместо \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}.
Input example #1
Output example #1
ADD 0 ADD 1 ADD 2 ADD 3 ADD 4 ADD 5 ADD 6 ADD 7 ADD 8 ADD 9 ADD 10 ADD 11 ADD 12 ADD 13 ADD 14 ADD 15 ADD 16 ADD 17 ADD 18 ADD 19 ADD 20 ADD 21 ADD 22 ADD 23 ADD 24 ADD 25 ADD 26 ADD 27 ADD 28 ADD 29 ADD 30 ADD 31 ADD 32 ADD 33 ADD 34 ADD 35 ADD 36 ADD 37 ADD 38 ADD 39 ADD 40 ADD 41 ADD 42 ADD 43 ADD 44 ADD 45 ADD 46 ADD 47 ADD 48 ADD 49 ADD 50 ADD 51 ADD 52 ADD 53 ADD 54 ADD 55 ADD 56 ADD 57 ADD 58 ADD 59 ADD 60 ADD 61 ADD 62 ADD 63 ADD 64 ADD 65 ADD 66 ADD 67 ADD 68 ADD 69 ADD 70 ADD 71 ADD 72 ADD 73 ADD 74 ADD 75 ADD 76 ADD 77 ADD 78 ADD 79 ADD 80 ADD 81 ADD 82 ADD 83 ADD 84 ADD 85 ADD 86 ADD 87 ADD 88 ADD 89 ADD 90 ADD 91 ADD 92 ADD 93 ADD 94 ADD 95 ADD 96 ADD 97 ADD 98 ADD 99 ADD 100 ADD 101 ADD 102 ADD 103 ADD 104 ADD 105 ADD 106 ADD 107 ADD 108 ADD 109 ADD 110 ADD 111 ADD 112 ADD 113 ADD 114 ADD 115 ADD 116 ADD 117 ADD 118 ADD 119 ADD 120 ADD 121 ADD 122 ADD 123 ADD 124 ADD 125 ADD 126 ADD 127 ADD 128 ADD 129 ADD 130 ADD 131 ADD 132 ADD 133 ADD 134 ADD 135 ADD 136 ADD 137 ADD 13 ...