結果

問題 No.2595 Parsing Challenge
コンテスト
ユーザー Kude
提出日時 2023-12-23 08:01:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,387 bytes
コンパイル時間 5,591 ms
コンパイル使用メモリ 324,728 KB
実行使用メモリ 238,684 KB
最終ジャッジ日時 2024-09-27 12:14:22
合計ジャッジ時間 37,268 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 25 WA * 27 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include <atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  } else
    return false;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  } else
    return false;
}
using ll = long long;
using P = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

constexpr int DIGIT = 6;
constexpr int BASE = 1000000;
struct lazy_bigint {
  vector<int> d;
  lazy_bigint() {}
  lazy_bigint(integral auto X) {
    while (X) {
      d.push_back(X % BASE);
      X /= BASE;
    }
  }
  lazy_bigint(string_view S) {
    if (S == "0") S = "";
    int L = S.size();
    bool neg = false;
    while (!S.empty() && (S.front() == '+' || S.front() == '-')) {
      neg ^= S.front() == '-';
      S = {S.begin() + 1, S.end()};
    }
    int dlen = (L + DIGIT - 1) / DIGIT;
    d = vector<int>(dlen);
    for (int i = 0; i < dlen; i++) {
      int l = i * DIGIT, r = min((i + 1) * DIGIT, L);
      int x = 0;
      for (int i = r - 1; i >= l; i--) {
        char c = S[L - 1 - i];
        assert(isdigit(c));
        x = 10 * x + (c - '0');
      }
      d[i] = x;
    }
    if (neg)
      for (int &x : d) x *= -1;
  }
  bool empty() const { return d.empty(); }
  int size() const { return d.size(); }
  int &operator[](int i) { return d[i]; }
  int operator[](int i) const { return d[i]; }
  void normalize() {
    if (empty()) return;
    assert(d.back());
    if (d.back() > 0) {
      bool borrow = false;
      for (int &x : d) {
        x -= borrow;
        borrow = x < 0;
        if (borrow) x += BASE;
      }
      assert(!borrow);
    } else {
      bool borrow = false;
      for (int &x : d) {
        x += borrow;
        borrow = x > 0;
        if (borrow) x -= BASE;
      }
      assert(!borrow);
    }
    while (!d.back()) d.pop_back();
  }
  string to_string() {
    normalize();
    if (empty()) return "0";
    string ans;
    for (int x : d) {
      x = abs(x);
      for (int i = 0; i < DIGIT; i++) {
        ans += '0' + x % 10;
        x /= 10;
      }
    }
    while (ans.back() == '0') ans.pop_back();
    if (d.back() < 0) ans += '-';
    ranges::reverse(ans);
    return ans;
  }
  friend istream &operator>>(istream &is, lazy_bigint &A) {
    string S;
    is >> S;
    A = lazy_bigint(S);
    return is;
  }
  friend ostream &operator<<(ostream &os, lazy_bigint &A) {
    return os << A.to_string();
  }
  template<bool minus>
  void plus_minus_core(const lazy_bigint& rhs) {
    int n = d.size(), m = rhs.d.size();
    d.resize(max(n, m));
    int carry = 0;
    for (int i = 0; i < m; i++) {
      if constexpr (!minus) d[i] += carry + rhs.d[i];
      else d[i] += carry - rhs.d[i];
      if (d[i] <= -BASE) carry = -1, d[i] += BASE;
      else if (d[i] >= BASE) carry = 1, d[i] -= BASE;
      else carry = 0;
    }
    if (carry) d.emplace_back(carry);
    while (!empty() && !d.back()) d.pop_back();
  }
  lazy_bigint& operator+=(const lazy_bigint& rhs) {
    plus_minus_core<false>(rhs);
    return *this;
  }
  lazy_bigint& operator-=(const lazy_bigint& rhs) {
    plus_minus_core<true>(rhs);
    return *this;
  }
  friend lazy_bigint operator+(const lazy_bigint &lhs, const lazy_bigint &rhs) {
    auto res = lhs;
    res += rhs;
    return res;
  }
  friend lazy_bigint operator-(const lazy_bigint &lhs, const lazy_bigint &rhs) {
    auto res = lhs;
    res -= rhs;
    return res;
  }
  friend lazy_bigint operator*(const lazy_bigint &A, const lazy_bigint &B) {
    if (A.empty() || B.empty()) return 0;
    int N = A.size();
    int M = B.size();
    vector<long long> a(N), b(M);
    for (int i = 0; i < N; i++) a[i] = A[i];
    for (int i = 0; i < M; i++) b[i] = B[i];
    auto C = atcoder::convolution_ll(a, b);
    long long carry = 0;
    for (int i = 0; i < N + M - 1; i++) {
      C[i] += carry;
      carry = C[i] / BASE;
      C[i] %= BASE;
    }
    while (carry) {
      C.push_back(carry % BASE);
      carry /= BASE;
    }
    while (C.back() == 0) C.pop_back();
    lazy_bigint ans;
    ans.d.resize(C.size());
    for (int i = 0; i < ssize(C); i++) ans[i] = C[i];
    return ans;
  }
  lazy_bigint& operator*=(const lazy_bigint &rhs) {
    return *this = *this * rhs;
  }
};

string s;
int ptr = 0;
lazy_bigint rd_expr();
optional<lazy_bigint> rd_term();
optional<lazy_bigint> rd_factor();
optional<lazy_bigint> rd_number();

optional<lazy_bigint> rd_number() {
  int l = ptr;
  while (isdigit(s[ptr])) ptr++;
  if (l == ptr) return {};
  lazy_bigint res({s.begin() + l, s.begin() + ptr});
  return res;
}
optional<lazy_bigint> rd_factor() {
  while (s[ptr] == '+') ptr++;
  if (s[ptr] == '-') {
    s[ptr] = '*';
    return -1;
  }
  optional<lazy_bigint> res;
  if (s[ptr] == '(') {
    ptr++;
    res = rd_expr();
    assert(s[ptr] == ')');
    ptr++;
  } else {
    res = rd_number();
  }
  return res;
}
optional<lazy_bigint> rd_term() {
  vector<lazy_bigint> facts;
  while (true) {
    optional<lazy_bigint> res = rd_factor();
    if (!res) break;
    facts.push_back(move(res.value()));
    if (s[ptr] != '*') break;
    ptr++;
  }
  if (facts.empty()) return {};
  static queue<lazy_bigint> q;
  while (facts.size()) {
    q.emplace(move(facts.back()));
    facts.pop_back();
  }
  while (q.size() >= 2) {
    auto a = move(q.front());
    q.pop();
    auto b = move(q.front());
    q.pop();
    q.emplace(a * b);
  }
  auto res = move(q.back());
  q.pop();
  return res;
}
lazy_bigint rd_expr() {
  vector<lazy_bigint> terms;
  while (true) {
    optional<lazy_bigint> res = rd_term();
    if (!res) break;
    terms.push_back(move(res.value()));
  }
  auto it = ranges::max_element(terms, less{}, [](const auto &x) { return x.size(); });
  auto res = move(*it);
  terms.erase(it);
  for (const auto& t : terms) res += t;
  return res;
}

}  // namespace
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n >> s;
  s += '$';
  auto ans = rd_expr();
  assert(ptr == n);
  cout << ans << '\n';
}
0