#939869 (C++14) No.2595 Parsing Challenge

提出ソース

結果

問題	No.2595 Parsing Challenge
ユーザー	👑 hos.lyric
提出日時	2023-12-23 00:57:21
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	896 ms / 6,000 ms
コード長	11,588 bytes
コンパイル時間	3,353 ms
コンパイル使用メモリ	165,660 KB
実行使用メモリ	218,796 KB
最終ジャッジ日時	2023-12-23 00:57:43
合計ジャッジ時間	21,697 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	14 ms 38,600 KB
testcase_01	AC	13 ms 38,600 KB
testcase_02	AC	13 ms 38,600 KB
testcase_03	AC	13 ms 38,600 KB
testcase_04	AC	14 ms 38,600 KB
testcase_05	AC	14 ms 38,600 KB
testcase_06	AC	13 ms 38,600 KB
testcase_07	AC	13 ms 38,600 KB
testcase_08	AC	13 ms 38,600 KB
testcase_09	AC	13 ms 38,600 KB
testcase_10	AC	14 ms 38,600 KB
testcase_11	AC	13 ms 38,600 KB
testcase_12	AC	13 ms 38,600 KB
testcase_13	AC	13 ms 38,600 KB
testcase_14	AC	14 ms 38,600 KB
testcase_15	AC	14 ms 38,600 KB
testcase_16	AC	15 ms 38,600 KB
testcase_17	AC	14 ms 38,600 KB
testcase_18	AC	14 ms 38,600 KB
testcase_19	AC	14 ms 38,600 KB
testcase_20	AC	18 ms 38,600 KB
testcase_21	AC	18 ms 38,600 KB
testcase_22	AC	18 ms 38,600 KB
testcase_23	AC	17 ms 38,600 KB
testcase_24	AC	19 ms 38,600 KB
testcase_25	AC	49 ms 39,112 KB
testcase_26	AC	57 ms 38,976 KB
testcase_27	AC	53 ms 38,968 KB
testcase_28	AC	54 ms 39,112 KB
testcase_29	AC	62 ms 39,112 KB
testcase_30	AC	377 ms 46,292 KB
testcase_31	AC	393 ms 46,236 KB
testcase_32	AC	405 ms 46,228 KB
testcase_33	AC	376 ms 46,564 KB
testcase_34	AC	387 ms 46,488 KB
testcase_35	AC	878 ms 67,240 KB
testcase_36	AC	896 ms 67,244 KB
testcase_37	AC	881 ms 67,236 KB
testcase_38	AC	870 ms 67,248 KB
testcase_39	AC	894 ms 67,244 KB
testcase_40	AC	35 ms 43,948 KB
testcase_41	AC	36 ms 43,948 KB
testcase_42	AC	36 ms 43,948 KB
testcase_43	AC	159 ms 218,796 KB
testcase_44	AC	233 ms 44,720 KB
testcase_45	AC	231 ms 44,720 KB
testcase_46	AC	232 ms 44,720 KB
testcase_47	AC	230 ms 44,720 KB
testcase_48	AC	233 ms 44,720 KB
testcase_49	AC	806 ms 50,056 KB
testcase_50	AC	779 ms 49,640 KB
testcase_51	AC	785 ms 49,624 KB
testcase_52	AC	603 ms 50,328 KB
testcase_53	AC	608 ms 50,460 KB
testcase_54	AC	602 ms 50,460 KB
testcase_55	AC	605 ms 50,288 KB
testcase_56	AC	612 ms 50,392 KB
testcase_57	AC	553 ms 142,112 KB
testcase_58	AC	555 ms 141,984 KB
testcase_59	AC	578 ms 141,984 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// https://github.com/SSRS-cp/yuki2595-bigint-lib
////////////////////////////////////////////////////////////////////////////////
#include <vector>
#include <string>
#include <atcoder/convolution>
const int DIGIT = 6;
const 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++;
  }
  for (int i = 0; i < M; i++){
    A[i] += B[i];
  }
  for (int i = 0; i < N - 1; i++){
    if (A[i] >= BASE){
      A[i] -= BASE;
      A[i + 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;
  }
  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 < C.size(); 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;
}
////////////////////////////////////////////////////////////////////////////////


constexpr int MAX_N = 1'000'010;

int N;
char S[MAX_N];

int U;
string T[MAX_N];
int L[MAX_N], R[MAX_N];
int newNode() {
  const int u = U++;
  T[u] = "";
  L[u] = R[u] = -1;
  return u;
}

int cur;
void eat(char c) {
  assert(S[cur] == c);
  ++cur;
}
int expr();
int term();
int fact();
int expr() {
  int ret = term();
  for (; S[cur] == '+' || S[cur] == '-'; ) {
    const char op = S[cur++];
    const int res = term();
    const int u = newNode();
    T[u] = string() + op;
    L[u] = ret;
    R[u] = res;
    ret = u;
  }
  return ret;
}
int term() {
  int ret = fact();
  for (; S[cur] == '*'; ) {
    const char op = S[cur++];
    const int res = fact();
    const int u = newNode();
    T[u] = string() + op;
    L[u] = ret;
    R[u] = res;
    ret = u;
  }
  return ret;
}
int fact() {
  int ret;
  if (S[cur] == '(') {
    eat('(');
    ret = expr();
    eat(')');
  } else {
    int sig = +1;
    for (; S[cur] == '-'; ) {
      eat('-');
      sig = -sig;
    }
    assert(isdigit(S[cur]));
    const int u = newNode();
    T[u] = "";
    if (sig < 0) {
      T[u] += "-";
    }
    for (; isdigit(S[cur]); ) {
      T[u] += S[cur++];
    }
    ret = u;
  }
  return ret;
}


vector<int> wts;

// x -> a x + b
struct Func {
  bigint a, b;
  Func(const bigint &a_, const bigint &b_) : a(a_), b(b_) {}
};
// f o g
Func mul(const Func &f, const Func &g) {
  return Func(f.a * g.a, f.a * g.b + f.b);
}
Func dc(const vector<Func> &fs, int l, int r) {
  if (l + 1 == r) {
    return fs[l];
  } else {
    const int mid = (l + r) / 2;
    return mul(dc(fs, l, mid), dc(fs, mid, r));
  }
}
bigint solve(int u) {
  vector<Func> fs;
  int v = u;
  for (; ; ) {
    if (~L[v]) {
      if (wts[L[v]] < wts[R[v]]) {
        const bigint res = solve(L[v]);
        switch (T[v][0]) {
          case '+': fs.emplace_back(bigint(1), res); break;
          case '-': fs.emplace_back(bigint(-1), res); break;
          case '*': fs.emplace_back(res, bigint(0)); break;
          default: assert(false);
        }
        v = R[v];
      } else {
        const bigint res = solve(R[v]);
        switch (T[v][0]) {
          case '+': fs.emplace_back(bigint(1), res); break;
          case '-': fs.emplace_back(bigint(1), -res); break;
          case '*': fs.emplace_back(res, bigint(0)); break;
          default: assert(false);
        }
        v = L[v];
      }
    } else {
      break;
    }
  }
  if (fs.size()) {
    const Func f = dc(fs, 0, (int)fs.size());
    return f.a * bigint(T[v]) + f.b;
  } else {
    return bigint(T[v]);
  }
}

int main() {
  for (; ~scanf("%d", &N); ) {
    scanf("%s", S);
    
    cur = 0;
    U = 0;
    const int rt = expr();
    
    wts.resize(U);
    for (int u = 0; u < U; ++u) {
      if (~L[u]) {
        wts[u] = wts[L[u]] + wts[R[u]];
      } else {
        wts[u] = T[u].size();
      }
    }
// cerr<<"T = ";pv(T,T+U);
// cerr<<"L = ";pv(L,L+U);
// cerr<<"R = ";pv(R,R+U);
// cerr<<"wts = "<<wts<<endl;
    const bigint ans = solve(rt);
    cout << ans << endl;
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード