Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <compare>
- #include <absl/time/time.h>
- #include <absl/time/clock.h>
- #include <sstream>
- #include <map>
- #include <regex>
- #include <absl/algorithm/container.h>
- #include <absl/strings/str_split.h>
- #include <absl/strings/str_cat.h>
- using namespace std;
- struct N {
- unique_ptr<N> left;
- unique_ptr<N> right;
- N *parent;
- unique_ptr<int> n;
- N() {};
- N(unique_ptr<N> &&l, unique_ptr<N> &&r, unique_ptr<int> &&n) :
- left(move(l)), right(move(r)),
- n(move(n)) {};
- };
- unique_ptr<N> FromLine(const string &l, N *parent) {
- auto n = make_unique<N>();
- if (l[0] == '[') {
- int p;
- int depth = 0;
- for (p = 1; p < l.length(); ++p) {
- if (l[p] == '[') ++depth;
- if (l[p] == ']') --depth;
- if (l[p] == ',' && depth == 0) {
- break;
- }
- }
- n->left = FromLine(l.substr(1, p - 1), n.get());
- n->right = FromLine(l.substr(p + 1, l.length() - p - 1), n.get());
- } else {
- n->n = make_unique<int>(l[0] - '0');
- }
- n->parent = parent;
- return n;
- }
- bool IsLeft(const N &n) {
- return n.parent != nullptr && n.parent->left.get() == &n;
- }
- bool IsRight(const N &n) {
- return n.parent != nullptr && n.parent->right.get() == &n;
- }
- void AddLeft(int x, N *n) {
- while (IsLeft(*n)) n = n->parent;
- if (!IsRight(*n)) return;
- // left sibling.
- n = n->parent->left.get();
- while (n->right != nullptr) n = n->right.get();
- *n->n += x;
- }
- void AddRight(int x, N *n) {
- while (IsRight(*n)) n = n->parent;
- if (!IsLeft(*n)) return;
- // right sibling.
- n = n->parent->right.get();
- while (n->left != nullptr) n = n->left.get();
- *n->n += x;
- }
- //[[[[3,0],[5,3]],[4,4]],[5,5]]
- bool Reduce(N *n, int d) {
- if (n == nullptr) return false;
- if (d == 4 && n->left != nullptr) {
- auto l = *n->left->n;
- auto r = *n->right->n;
- AddLeft(l, n->left.get());
- AddRight(r, n->right.get());
- n->left.reset(nullptr);
- n->right.reset(nullptr);
- n->n = make_unique<int>(0);
- return true;
- }
- if (Reduce(n->left.get(), d + 1)) {
- return true;
- }
- return Reduce(n->right.get(), d + 1);
- }
- bool Split(N *n) {
- if (n == nullptr) return false;
- if (n->n != nullptr && *n->n >= 10) {
- int x = *n->n;
- n->n.reset(nullptr);
- n->left = make_unique<N>();
- n->left->n = make_unique<int>(x / 2);
- n->left->parent = n;
- n->right = make_unique<N>();
- n->right->n = make_unique<int>(x / 2 + x % 2);
- n->right->parent = n;
- return true;
- }
- if (Split(n->left.get())) return true;
- return Split(n->right.get());
- }
- void print(const N &n) {
- if (n.left != nullptr) {
- cout << '[';
- print(*n.left);
- cout << ',';
- print(*n.right);
- cout << ']';
- } else {
- cout << *n.n;
- }
- }
- void ReduceAll(N *n) {
- cout << "REDUCING" << endl;
- print(*n);
- cout << endl;
- while (true) {
- if (Reduce(n, 0)) continue;
- if (Split(n)) continue;
- break;
- }
- print(*n);
- cout << endl;
- }
- int Magnitude(const N &n) {
- if (n.n != nullptr) return *n.n;
- return 3 * Magnitude(*n.left) + 2 * Magnitude(*n.right);
- }
- unique_ptr<N> Copy(N *n) {
- auto c = make_unique<N>();
- if (n->left != nullptr) {
- c->left = Copy(n->left.get());
- c->left->parent = c.get();
- }
- if (n->right != nullptr) {
- c->right = Copy(n->right.get());
- c->right->parent = c.get();
- }
- if (n->n != nullptr) c->n = make_unique<int>(*n->n);
- return c;
- }
- unique_ptr<N> Plus(N *l, N *r) {
- auto n = make_unique<N>();
- n->left = Copy(l);
- n->right = Copy(r);
- n->left->parent = n.get();
- n->right->parent = n.get();
- n->parent = nullptr;
- return n;
- }
- int main() {
- auto start = absl::Now();
- int ans = 0;
- std::string line;
- vector<unique_ptr<N>> all_n;
- for (; std::getline(std::cin, line);) {
- all_n.push_back(FromLine(line, nullptr));
- }
- for (int i = 0; i < all_n.size(); ++i) {
- for (int j = 0; j < all_n.size(); ++j) {
- if (i == j) continue;
- auto sum = Plus(all_n[i].get(), all_n[j].get());
- ReduceAll(sum.get());
- ans = max(ans, Magnitude(*sum));
- }
- }
- cout << ans << endl;
- cout << absl::Now() - start << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment