#936889 (C++17) No.2595 Parsing Challenge

提出ソース

結果

問題	No.2595 Parsing Challenge
ユーザー	SSRS
提出日時	2023-12-06 17:04:41
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	10,193 bytes
コンパイル時間	4,738 ms
コンパイル使用メモリ	265,508 KB
実行使用メモリ	184,076 KB
最終ジャッジ日時	2024-09-27 11:35:00
合計ジャッジ時間	23,134 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	WA	-
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	WA	-
testcase_11	AC	3 ms 6,944 KB
testcase_12	WA	-
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	AC	909 ms 65,100 KB
testcase_36	AC	900 ms 65,696 KB
testcase_37	AC	913 ms 65,504 KB
testcase_38	AC	903 ms 65,108 KB
testcase_39	AC	912 ms 65,656 KB
testcase_40	AC	40 ms 9,592 KB
testcase_41	AC	40 ms 9,588 KB
testcase_42	AC	39 ms 9,712 KB
testcase_43	AC	182 ms 184,076 KB
testcase_44	AC	281 ms 36,272 KB
testcase_45	AC	287 ms 36,340 KB
testcase_46	AC	281 ms 36,392 KB
testcase_47	AC	280 ms 36,368 KB
testcase_48	AC	277 ms 36,384 KB
testcase_49	AC	788 ms 43,012 KB
testcase_50	AC	790 ms 43,024 KB
testcase_51	AC	801 ms 43,288 KB
testcase_52	AC	649 ms 59,920 KB
testcase_53	AC	646 ms 59,300 KB
testcase_54	AC	638 ms 60,164 KB
testcase_55	AC	662 ms 59,848 KB
testcase_56	AC	643 ms 60,436 KB
testcase_57	AC	598 ms 149,948 KB
testcase_58	AC	601 ms 149,628 KB
testcase_59	AC	596 ms 151,120 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/convolution>
using namespace std;
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;
}
struct parser{
  int V = 0;
  vector<vector<int>> c;
  vector<string> s;
  parser(string &S){
    int p = 0;
    expr(S, p);
  }
  int number(string &S, int &p){
    string tmp;
    if (S[p] == '-'){
      tmp += S[p];
      p++;
    }
    while (isdigit(S[p]) != 0){
      tmp += S[p];
      p++;
    }
    c.push_back(vector<int>(0));
    s.push_back(tmp);
    V++;
    return V - 1;
  }
  int factor(string &S, int &p){
    if (isdigit(S[p]) != 0 || S[p] == '-'){
      return number(S, p);
    } else {
      p++;
      int ans = expr(S, p);
      p++;
      return ans;
    }
  }
  int term(string &S, int &p){
    int ans = factor(S, p);
    while (S[p] == '*'){
      p++;
      int ans2 = factor(S, p);
      c.push_back(vector<int>{ans, ans2});
      s.push_back("*");
      V++;
      ans = V - 1;
    }
    return ans;
  }
  int expr(string &S, int &p){
    int ans = term(S, p);
    while (S[p] == '+' || S[p] == '-'){
      char op = S[p];
      p++;
      int ans2 = term(S, p);
      c.push_back(vector<int>{ans, ans2});
      s.push_back(string(1, op));
      V++;
      ans = V - 1;
    }
    return ans;
  }
};
int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  parser P(S);
  vector<int> sz(P.V);
  for (int i = 0; i < P.V; i++){
    if (P.c[i].empty()){
      sz[i] = P.s[i].size();
    } else {
      sz[i] = sz[P.c[i][0]] + sz[P.c[i][1]];
    }
  }
  vector<bool> head(P.V, false);
  head[P.V - 1] = true;
  for (int i = 0; i < P.V; i++){
    if (!P.c[i].empty()){
      if (sz[P.c[i][0]] < sz[P.c[i][1]]){
        swap(P.c[i][0], P.c[i][1]);
        if (P.s[i] == "-"){
          P.s[i] = "--";
        }
      }
      head[P.c[i][1]] = true;
    }
  }
  vector<bigint> dp(P.V);
  for (int i = 0; i < P.V; i++){
    if (head[i]){
      vector<int> id;
      for (int v = i; ; v = P.c[v][0]){
        id.push_back(v);
        if (P.c[v].empty()){
          break;
        }
      }
      dp[i] = bigint(P.s[id.back()]);
      id.pop_back();
      if (!id.empty()){
        int cnt = id.size();
        vector<pair<bigint, bigint>> F(cnt);
        for (int j = 0; j < cnt; j++){
          int v = id[j];
          if (P.s[v] == "+"){
            F[j] = make_pair(1, dp[P.c[v][1]]);
          }
          if (P.s[v] == "-"){
            F[j] = make_pair(1, -dp[P.c[v][1]]);
          }
          if (P.s[v] == "--"){
            F[j] = make_pair(-1, dp[P.c[v][1]]);
          }
          if (P.s[v] == "*"){
            F[j] = make_pair(dp[P.c[v][1]], 0);
          }
        }
        auto dfs = [&](auto dfs, int L, int R) -> pair<bigint, bigint> {
          if (R - L == 1){
            return F[L];
          } else {
            int m = (L + R) / 2;
            pair<bigint, bigint> ansL = dfs(dfs, L, m);
            pair<bigint, bigint> ansR = dfs(dfs, m, R);
            return make_pair(ansL.first * ansR.first, ansL.first * ansR.second + ansL.second);
          }
        };
        pair<bigint, bigint> ans = dfs(dfs, 0, cnt);
        dp[i] = dp[i] * ans.first + ans.second;
      }
    }
  }
  cout << dp[P.V - 1] << endl;
}

yukicoder

結果

テストケース

ソースコード