結果

問題 No.2595 Parsing Challenge
ユーザー SSRSSSRS
提出日時 2023-12-06 17:04:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 3,142 bytes
コンパイル時間 2,876 ms
コンパイル使用メモリ 221,432 KB
実行使用メモリ 183,952 KB
最終ジャッジ日時 2024-09-27 11:33:32
合計ジャッジ時間 14,166 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 RE -
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 RE -
testcase_11 AC 2 ms
6,940 KB
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 AC 188 ms
183,952 KB
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
権限があれば一括ダウンロードができます

ソースコード

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