ErnestGalbrun

Untitled

Dec 19th, 2021
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <compare>
  5. #include <absl/time/time.h>
  6. #include <absl/time/clock.h>
  7. #include <sstream>
  8. #include <map>
  9. #include <regex>
  10. #include <absl/algorithm/container.h>
  11. #include <absl/strings/str_split.h>
  12. #include <absl/strings/str_cat.h>
  13.  
  14. using namespace std;
  15.  
  16. struct N {
  17. unique_ptr<N> left;
  18. unique_ptr<N> right;
  19. N *parent;
  20. unique_ptr<int> n;
  21.  
  22. N() {};
  23.  
  24. N(unique_ptr<N> &&l, unique_ptr<N> &&r, unique_ptr<int> &&n) :
  25. left(move(l)), right(move(r)),
  26. n(move(n)) {};
  27. };
  28.  
  29. unique_ptr<N> FromLine(const string &l, N *parent) {
  30. auto n = make_unique<N>();
  31. if (l[0] == '[') {
  32. int p;
  33. int depth = 0;
  34. for (p = 1; p < l.length(); ++p) {
  35. if (l[p] == '[') ++depth;
  36. if (l[p] == ']') --depth;
  37. if (l[p] == ',' && depth == 0) {
  38. break;
  39. }
  40. }
  41. n->left = FromLine(l.substr(1, p - 1), n.get());
  42. n->right = FromLine(l.substr(p + 1, l.length() - p - 1), n.get());
  43. } else {
  44. n->n = make_unique<int>(l[0] - '0');
  45. }
  46. n->parent = parent;
  47. return n;
  48. }
  49.  
  50. bool IsLeft(const N &n) {
  51. return n.parent != nullptr && n.parent->left.get() == &n;
  52. }
  53.  
  54. bool IsRight(const N &n) {
  55. return n.parent != nullptr && n.parent->right.get() == &n;
  56. }
  57.  
  58. void AddLeft(int x, N *n) {
  59. while (IsLeft(*n)) n = n->parent;
  60. if (!IsRight(*n)) return;
  61. // left sibling.
  62. n = n->parent->left.get();
  63. while (n->right != nullptr) n = n->right.get();
  64. *n->n += x;
  65. }
  66.  
  67. void AddRight(int x, N *n) {
  68. while (IsRight(*n)) n = n->parent;
  69. if (!IsLeft(*n)) return;
  70. // right sibling.
  71. n = n->parent->right.get();
  72. while (n->left != nullptr) n = n->left.get();
  73. *n->n += x;
  74. }
  75.  
  76. //[[[[3,0],[5,3]],[4,4]],[5,5]]
  77.  
  78. bool Reduce(N *n, int d) {
  79. if (n == nullptr) return false;
  80. if (d == 4 && n->left != nullptr) {
  81. auto l = *n->left->n;
  82. auto r = *n->right->n;
  83. AddLeft(l, n->left.get());
  84. AddRight(r, n->right.get());
  85. n->left.reset(nullptr);
  86. n->right.reset(nullptr);
  87. n->n = make_unique<int>(0);
  88. return true;
  89. }
  90.  
  91. if (Reduce(n->left.get(), d + 1)) {
  92. return true;
  93. }
  94. return Reduce(n->right.get(), d + 1);
  95. }
  96.  
  97. bool Split(N *n) {
  98. if (n == nullptr) return false;
  99. if (n->n != nullptr && *n->n >= 10) {
  100. int x = *n->n;
  101. n->n.reset(nullptr);
  102. n->left = make_unique<N>();
  103. n->left->n = make_unique<int>(x / 2);
  104. n->left->parent = n;
  105. n->right = make_unique<N>();
  106. n->right->n = make_unique<int>(x / 2 + x % 2);
  107. n->right->parent = n;
  108. return true;
  109. }
  110.  
  111. if (Split(n->left.get())) return true;
  112. return Split(n->right.get());
  113. }
  114.  
  115. void print(const N &n) {
  116. if (n.left != nullptr) {
  117. cout << '[';
  118. print(*n.left);
  119. cout << ',';
  120. print(*n.right);
  121. cout << ']';
  122. } else {
  123. cout << *n.n;
  124. }
  125. }
  126.  
  127. void ReduceAll(N *n) {
  128. cout << "REDUCING" << endl;
  129. print(*n);
  130. cout << endl;
  131. while (true) {
  132. if (Reduce(n, 0)) continue;
  133. if (Split(n)) continue;
  134. break;
  135. }
  136. print(*n);
  137. cout << endl;
  138. }
  139.  
  140. int Magnitude(const N &n) {
  141. if (n.n != nullptr) return *n.n;
  142. return 3 * Magnitude(*n.left) + 2 * Magnitude(*n.right);
  143. }
  144.  
  145. unique_ptr<N> Copy(N *n) {
  146. auto c = make_unique<N>();
  147. if (n->left != nullptr) {
  148. c->left = Copy(n->left.get());
  149. c->left->parent = c.get();
  150. }
  151. if (n->right != nullptr) {
  152. c->right = Copy(n->right.get());
  153. c->right->parent = c.get();
  154. }
  155. if (n->n != nullptr) c->n = make_unique<int>(*n->n);
  156. return c;
  157. }
  158.  
  159. unique_ptr<N> Plus(N *l, N *r) {
  160. auto n = make_unique<N>();
  161. n->left = Copy(l);
  162. n->right = Copy(r);
  163. n->left->parent = n.get();
  164. n->right->parent = n.get();
  165. n->parent = nullptr;
  166. return n;
  167. }
  168.  
  169. int main() {
  170. auto start = absl::Now();
  171.  
  172. int ans = 0;
  173. std::string line;
  174. vector<unique_ptr<N>> all_n;
  175. for (; std::getline(std::cin, line);) {
  176. all_n.push_back(FromLine(line, nullptr));
  177. }
  178. for (int i = 0; i < all_n.size(); ++i) {
  179. for (int j = 0; j < all_n.size(); ++j) {
  180. if (i == j) continue;
  181. auto sum = Plus(all_n[i].get(), all_n[j].get());
  182. ReduceAll(sum.get());
  183. ans = max(ans, Magnitude(*sum));
  184. }
  185. }
  186. cout << ans << endl;
  187. cout << absl::Now() - start << endl;
  188.  
  189. return 0;
  190. }
Advertisement
Add Comment
Please, Sign In to add comment