結果

問題 No.2595 Parsing Challenge
ユーザー SSRS
提出日時 2023-12-06 17:04:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 3,142 bytes
コンパイル時間 3,325 ms
コンパイル使用メモリ 212,876 KB
最終ジャッジ日時 2025-02-18 08:35:20
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 RE * 1
other AC * 7 WA * 16 RE * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
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<long long> 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] = stoll(P.s[id.back()]);
      id.pop_back();
      if (!id.empty()){
        int cnt = id.size();
        vector<pair<long long, long long>> 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<long long, long long> {
          if (R - L == 1){
            return F[L];
          } else {
            int m = (L + R) / 2;
            pair<long long, long long> ansL = dfs(dfs, L, m);
            pair<long long, long long> ansR = dfs(dfs, m, R);
            return make_pair(ansL.first * ansR.first, ansL.first * ansR.second + ansL.second);
          }
        };
        pair<long long, long long> ans = dfs(dfs, 0, cnt);
        dp[i] = dp[i] * ans.first + ans.second;
      }
    }
  }
  cout << dp[P.V - 1] << endl;
}
0