結果

問題 No.2595 Parsing Challenge
ユーザー KudeKude
提出日時 2023-12-23 12:50:53
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 11,642 bytes
コンパイル時間 5,767 ms
コンパイル使用メモリ 328,620 KB
実行使用メモリ 176,344 KB
最終ジャッジ日時 2024-09-27 12:22:23
合計ジャッジ時間 47,042 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,948 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 5 ms
6,940 KB
testcase_21 AC 4 ms
6,944 KB
testcase_22 AC 4 ms
6,940 KB
testcase_23 AC 4 ms
6,944 KB
testcase_24 AC 4 ms
6,944 KB
testcase_25 AC 22 ms
6,940 KB
testcase_26 AC 26 ms
6,940 KB
testcase_27 AC 26 ms
6,940 KB
testcase_28 AC 25 ms
6,940 KB
testcase_29 AC 26 ms
6,940 KB
testcase_30 AC 215 ms
6,944 KB
testcase_31 AC 221 ms
6,940 KB
testcase_32 AC 224 ms
6,940 KB
testcase_33 AC 210 ms
6,940 KB
testcase_34 AC 217 ms
6,944 KB
testcase_35 AC 670 ms
30,020 KB
testcase_36 AC 677 ms
30,692 KB
testcase_37 AC 665 ms
30,120 KB
testcase_38 AC 671 ms
29,900 KB
testcase_39 AC 665 ms
31,120 KB
testcase_40 AC 17 ms
8,140 KB
testcase_41 AC 16 ms
8,016 KB
testcase_42 AC 16 ms
8,012 KB
testcase_43 AC 187 ms
176,344 KB
testcase_44 AC 173 ms
6,940 KB
testcase_45 AC 175 ms
6,944 KB
testcase_46 AC 173 ms
6,940 KB
testcase_47 AC 173 ms
6,944 KB
testcase_48 AC 175 ms
6,940 KB
testcase_49 AC 733 ms
9,588 KB
testcase_50 AC 732 ms
9,320 KB
testcase_51 AC 739 ms
9,260 KB
testcase_52 AC 4,910 ms
9,176 KB
testcase_53 AC 5,039 ms
9,308 KB
testcase_54 AC 4,892 ms
9,312 KB
testcase_55 AC 5,047 ms
9,308 KB
testcase_56 AC 4,687 ms
9,180 KB
testcase_57 TLE -
testcase_58 -- -
testcase_59 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:359:8: warning: '{anonymous}::bigint {anonymous}::operator-(const bigint&, const bigint&)' defined but not used [-Wunused-function]
  359 | bigint operator -(const bigint &A, const bigint &B){
      |        ^~~~~~~~
main.cpp:338:8: warning: '{anonymous}::bigint {anonymous}::operator+(const bigint&, const bigint&)' defined but not used [-Wunused-function]
  338 | bigint operator +(const bigint &A, const bigint &B){
      |        ^~~~~~~~
main.cpp:315:8: warning: '{anonymous}::bigint {anonymous}::operator-(const bigint&)' defined but not used [-Wunused-function]
  315 | bigint operator -(const bigint &A){
      |        ^~~~~~~~
main.cpp:312:8: warning: '{anonymous}::bigint {anonymous}::operator+(const bigint&)' defined but not used [-Wunused-function]
  312 | bigint operator +(const bigint &A){
      |        ^~~~~~~~
main.cpp:309:6: warning: 'bool {anonymous}::operator>=(const bigint&, const bigint&)' defined but not used [-Wunused-function]
  309 | bool operator >=(const bigint &A, const bigint &B){
      |      ^~~~~~~~
main.cpp:306:6: warning: 'bool {anonymous}::operator<=(const bigint&, const bigint&)' defined but not used [-Wunused-function]
  306 | bool operator <=(const bigint &A, const bigint &B){
      |      ^~~~~~~~
main.cpp:303:6: warning: 'bool {anonymous}::operator>(const bigint&, const bigint&)' defined but not used [-Wunused-function]
  303 | bool operator >(const bigint &A, const bigint &B){
      |      ^~~~~~~~
main.cpp:300:6: warning: 'bool {anonymous}::operator<(const bigint&, const bigint&)' defined but not used [-Wunused-function]
  300 | bool operator <(const bigint &A, const bigint &B){
      |      ^~~~~~~~
main.cpp:297:6: warning: 'bool {anonymous}::operator!=(const bigint&, const bigint&)' defined but not used [-Wunused-function]
  297 | bool operator !=(const bigint &A, const bigint &B){
      |      ^~~~~~~~
main.cpp:294:6: warning: 'bool {anonymous}::operator==(const bigint&, const bigint&)' defined but not used [-Wunused-fu

ソースコード

diff # 

#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 positive_bigint{
  std::vector<int> d;
  positive_bigint(){
  }
  positive_bigint(long long X){
    while (X > 0){
      d.push_back(X % BASE);
      X /= BASE;
    }
  }
  positive_bigint(std::string S){
    if (S == "0"){
      S = "";
    }
    int L = S.size();
    d.resize((L + DIGIT - 1) / DIGIT, 0);
    for (int i = L - 1; i >= 0; i -= 6){
      for (int j = std::max(i - 5, 0); j <= i; j++){
        d[i / DIGIT] *= 10;
        d[i / DIGIT] += S[j] - '0';
      }
    }
    std::reverse(d.begin(), d.end());
  }
  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];
  }
};
std::string to_string(const positive_bigint &A){
  int N = A.size();
  std::string ans;
  for (int i = N - 1; i >= 0; i--){
    std::string tmp = std::to_string(A[i]);
    if (i < N - 1){
      ans += std::string(DIGIT - tmp.size(), '0');
    }
    ans += tmp;
  }
  if (ans.empty()){
    ans = "0";
  }
  return ans;
}
std::istream& operator >>(std::istream &is, positive_bigint &A){
  std::string S;
  is >> S;
  A = positive_bigint(S);
  return is;
}
std::ostream& operator <<(std::ostream &os, positive_bigint &A){
  os << to_string(A);
  return os;
}
int cmp(const positive_bigint &A, const positive_bigint &B){
  int N = A.size();
  int M = B.size();
  if (N < M){
    return -1;
  } else if (N > M){
    return 1;
  } else {
    for (int i = N - 1; i >= 0; i--){
      if (A[i] < B[i]){
        return -1;
      }
      if (A[i] > B[i]){
        return 1;
      }
    }
    return 0;
  }
}
bool operator ==(const positive_bigint &A, const positive_bigint &B){
  return cmp(A, B) == 0;
}
bool operator !=(const positive_bigint &A, const positive_bigint &B){
  return cmp(A, B) != 0;
}
bool operator <(const positive_bigint &A, const positive_bigint &B){
  return cmp(A, B) < 0;
}
bool operator >(const positive_bigint &A, const positive_bigint &B){
  return cmp(A, B) > 0;
}
bool operator <=(const positive_bigint &A, const positive_bigint &B){
  return cmp(A, B) <= 0;
}
bool operator >=(const positive_bigint &A, const positive_bigint &B){
  return cmp(A, B) >= 0;
}
positive_bigint& operator +=(positive_bigint &A, const positive_bigint &B){
  int N = A.size();
  int M = B.size();
  while (N < M){
    A.d.push_back(0);
    N++;
  }
  // ?
  bool carry = false;
  for (int i = 0; i < M; i++) {
    A[i] += B[i] + carry;
    carry = A[i] >= BASE;
    if (carry) A[i] -= BASE;
  }
  if (carry) {
    int i = M;
    for (; i < N; i++) {
      if (A[i] < BASE - 1) {
        A[i]++;
        break;
      }
      A[i] = 0;
    }
    if (i == N) A.d.push_back(1);
  }
  // if (N > 0){
  //   if (A[N - 1] >= BASE){
  //     A.d.push_back(1);
  //     A[N - 1] -= BASE;
  //   }
  // }
  return A;
}
positive_bigint operator +(const positive_bigint &A, const positive_bigint &B){
  positive_bigint A2 = A;
  A2 += B;
  return A2;
}
positive_bigint& operator -=(positive_bigint &A, const positive_bigint &B){
  int N = A.size();
  int M = B.size();
  for (int i = 0; i < M; i++){
    A[i] -= B[i];
  }
  for (int i = 0; i < N - 1; i++){
    if (A[i] < 0){
      A[i] += BASE;
      A[i + 1]--;
    }
  }
  while (!A.empty()){
    if (A.d.back() == 0){
      A.d.pop_back();
    } else {
      break;
    }
  }
  return A;
}
positive_bigint operator -(const positive_bigint &A, const positive_bigint &B){
  positive_bigint A2 = A;
  A2 -= B;
  return A2;
}
positive_bigint operator *(const positive_bigint &A, const positive_bigint &B){
  if (A.empty() || B.empty()){
    return 0;
  }
  int N = A.size();
  int M = B.size();
  std::vector<long long> a(N);
  for (int i=  0; i < N; i++){
    a[i] = A[i];
  }
  std::vector<long long> b(M);
  for (int i = 0; i < M; i++){
    b[i] = B[i];
  }
  std::vector<long long> C = atcoder::convolution_ll(a, b);
  for (int i = 0; i < N + M - 2; i++){
    C[i + 1] += C[i] / BASE;
    C[i] %= BASE;
  }
  while (C.back() >= BASE) {
    long long x = C.back();
    C.back() = x % BASE;
    C.push_back(x / BASE);
  }
  // if (C[N + M - 2] >= BASE){
  //   C.resize(N + M);
  //   C[N + M - 1] += C[N + M - 2] / BASE;
  //   C[N + M - 2] %= BASE;
  // }
  positive_bigint ans;
  ans.d.resize(C.size());
  for (int i = 0; i < ssize(C); i++){
    ans[i] = C[i];
  }
  return ans;
}
positive_bigint operator *=(positive_bigint &A, const positive_bigint &B){
  A = A * B;
  return A;
}
struct bigint{
  bool neg = false;
  positive_bigint a;
  bigint(){
  }
  bigint(long long X): neg(X < 0), a(abs(X)){
  }
  bigint(const positive_bigint &X, bool neg = false): neg(neg), a(X){
  }
  bigint(const std::string &s){
    if (!s.empty()){
      if (s[0] == '-'){
        neg = true;
        a = positive_bigint(s.substr(1, s.size() - 1));
      } else {
        a = positive_bigint(s);
      }
    }
  }
  bool empty() const {
    return a.empty();
  }
  int size() const {
    return a.size();
  }
  int& operator [](int i){
    return a[i];
  }
};
std::string to_string(const bigint &A){
  std::string ans;
  if (A.neg){
    ans += '-';
  }
  ans += to_string(A.a);
  return ans;
}
std::istream& operator >>(std::istream &is, bigint &A){
  std::string S;
  is >> S;
  if (S != "0"){
    A = bigint(S);
  }
  return is;
}
std::ostream& operator <<(std::ostream &os, bigint A){
  os << to_string(A);
  return os;
}
positive_bigint abs(const bigint &A){
  return A.a;
}
int cmp(const bigint &A, const bigint &B){
  if (!A.neg){
    if (!B.neg){
      return cmp(A.a, B.a);
    } else {
      return 1;
    }
  } else {
    if (!B.neg){
      return -1;
    } else {
      return cmp(B.a, A.a);
    }
  }
}
bool operator ==(const bigint &A, const bigint &B){
  return cmp(A, B) == 0;
}
bool operator !=(const bigint &A, const bigint &B){
  return cmp(A, B) != 0;
}
bool operator <(const bigint &A, const bigint &B){
  return cmp(A, B) < 0;
}
bool operator >(const bigint &A, const bigint &B){
  return cmp(A, B) > 0;
}
bool operator <=(const bigint &A, const bigint &B){
  return cmp(A, B) <= 0;
}
bool operator >=(const bigint &A, const bigint &B){
  return cmp(A, B) >= 0;
}
bigint operator +(const bigint &A){
  return A;
}
bigint operator -(const bigint &A){
  bigint A2 = A;
  if (!A2.empty()){
    A2.neg = !A2.neg;
  }
  return A2;
}
bigint& operator +=(bigint &A, const bigint &B){
  if (A.neg == B.neg){
    A.a += B.a;
  } else {
    int c = cmp(A.a, B.a);
    if (c > 0){
      A.a -= B.a;
    } else if (c < 0){
      A.a = B.a - A.a;
      A.neg = !A.neg;
    } else {
      A = 0;
    }
  }
  return A;
}
bigint operator +(const bigint &A, const bigint &B){
  bigint A2 = A;
  A2 += B;
  return A2;
}
bigint& operator -=(bigint &A, const bigint &B){
  if (A.neg != B.neg){
    A.a += B.a;
  } else {
    int c = cmp(A.a, B.a);
    if (c > 0){
      A.a -= B.a;
    } else if (c < 0){
      A.a = B.a - A.a;
      A.neg = !A.neg;
    } else {
      A = 0;
    }
  }
  return A;
}
bigint operator -(const bigint &A, const bigint &B){
  bigint A2 = A;
  A2 -= B;
  return A2;
}
bigint operator *=(bigint &A, const bigint &B){
  if (A.empty() || B.empty()){
    A = 0;
  } else {
    if (B.neg){
      A.neg = !A.neg;
    }
    A.a *= B.a;
  }
  return A;
}
bigint operator *(const bigint &A, const bigint &B){
  bigint A2 = A;
  A2 *= B;
  return A2;
}

struct T {
  vector<bigint> factors;
  int sz;
  bigint eval() {
    assert(!factors.empty());
    // if (fac.size() == 1) return;
    // if (op == OP::ADD) {
      // auto it = ranges::max_element(d, less{}, [](const auto& x) { return x.size(); });
      // auto res = move(*it);
      // d.erase(it);
      // for (const auto& t : d) res += t;
      // d.clear();
      // d.push_back(move(res));
    // } else {
    static vector<bigint> q, nq;
    q.clear();
    nq.clear();
    for (auto& t : factors) q.push_back(move(t));
    // d.clear();
    while (q.size() >= 2) {
      while (q.size() >= 2) {
        auto a = move(q.back()); q.pop_back();
        auto b = move(q.back()); q.pop_back();
        nq.push_back(a * b);
      }
      if (q.size()) nq.push_back(move(q.back())), q.pop_back();
      swap(q, nq);
    }
    return move(q.back());
  }
};
struct S {
  vector<T> d;
  void mul(bigint x) {
    int dsz = x.size();
    for (auto& t : d) {
      t.factors.push_back(x);
      t.sz += dsz;
    }
    for (int i = ssize(d) - 2; i >= 0; i--) {
      if (d[i].sz <= 2 * d[i+1].sz) {
        auto a = d[i].eval();
        auto b = d[i+1].eval();
        if (a.size() < b.size()) swap(a, b);
        a += b;
        d.erase(d.begin() + i + 1);
        d[i].sz = a.size();
        d[i].factors.clear();
        d[i].factors.push_back(move(a));
      }
    }
  }
  void add(bigint x) {
    while (!d.empty() && d.back().sz <= 2 * x.size()) {
      auto a = d.back().eval();
      d.pop_back();
      if (x.size() < a.size()) swap(x, a);
      x += a;
    }
    d.emplace_back();
    d.back().sz = x.size();
    d.back().factors.push_back({move(x)});
  }
  bigint eval() {
    bigint res;
    for (auto& t : d) {
      auto a = t.eval();
      if (res.size() < a.size()) swap(res, a);
      res += a;
    }
    return res;
  }
  int size() {
    int res = 0;
    for (const auto& t : d) res += t.sz;
    return res;
  }
};

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

optional<S> rd_number() {
  int l = ptr;
  while (isdigit(s[ptr])) ptr++;
  if (l == ptr) return {};
  bigint res = s.substr(l, ptr - l);
  int sz = res.size();
  return S{vector<T>{T{vector<bigint>{move(res)}, sz}}};
}
optional<S> rd_factor() {
  bool neg = false;
  while (s[ptr] == '+') ptr++;
  while (s[ptr] == '-') neg ^= 1, ptr++;
  optional<S> res;
  if (s[ptr] == '(') {
    ptr++;
    res = rd_expr();
    assert(s[ptr] == ')');
    ptr++;
  } else {
    res = rd_number();
  }
  if (neg) {
    assert(res.has_value());
    res.value().mul(-1);
    // if (res.value().op == OP::ADD) res.value().eval();
    // res.value().d.front().neg ^= 1;
  }
  return res;
}
optional<S> rd_term() {
  optional<S> x;
  while (true) {
    optional<S> res = rd_factor();
    if (!res) break;
    if (!x) {
      x = move(res);
    } else {
      if (x.value().size() < res.value().size()) swap(x, res);
      x.value().mul(res.value().eval());
    }
    if (s[ptr] != '*') break;
    ptr++;
  }
  return x;
}
S rd_expr() {
  optional<S> x;
  while (true) {
    optional<S> res = rd_term();
    if (!res) break;
    if (!x) {
      x = move(res);
    } else {
      if (x.value().size() < res.value().size()) swap(x, res);
      x.value().add(res.value().eval());
    }
  }
  assert(x.has_value());
  return x.value();
}

} 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.eval() << '\n';
}
0