結果

問題 No.2595 Parsing Challenge
コンテスト
ユーザー hiro1729
提出日時 2023-12-23 08:08:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 14,527 bytes
コンパイル時間 6,061 ms
コンパイル使用メモリ 317,056 KB
実行使用メモリ 814,804 KB
最終ジャッジ日時 2024-09-27 12:15:25
合計ジャッジ時間 14,604 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 5 WA * 25 MLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#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;
}


using namespace std;


// Parser (T must have constructor T(long long))
template<class T> struct Parser {
    /* basic settings */
    vector<vector<string>> OPERATORS;               // binary operator priority
    function<T(const string&, T, T)> OPERATION;     // binary operation

    /* optional settings */
    function<T(const string&, int&)> GET_LEAF;      // leaf parser
    vector<string> UNARY_OPERATORS;                 // unary operator (ex: "-", "log")
    function<T(const string&, T)> UNARY_OPERATION;  // unary operation
    const string OPERATOR_NUMBER = "num";
    
    /* results */
    string S;
    int root;                    // vals[root] is the answer
    vector<T> vals;              // value of each node
    vector<string> ops;          // operator of each node
    vector<int> left, right;     // the index of left-node, right-node
    vector<int> ids;             // the node-index of i-th value
    
    /* constructor */
    Parser() {}
    Parser(const vector<vector<string>> &operators,
           const function<T(const string&, T, T)> operation) {
        init(operators, operation);
    }
    Parser(const vector<vector<string>> &operators,
           const function<T(const string&, T, T)> operation,
           const function<T(const string&, int&)> get_leaf) {
        init(operators, operation, get_leaf);
    }
    Parser(const vector<vector<string>> &operators,
           const function<T(const string&, T, T)> operation,
           const function<T(const string&, int&)> get_leaf,
           const vector<string> &unary_operators,
           const function<T(const string &op, T)> unary_operation) {
        init(operators, operation, get_leaf, unary_operators, unary_operation);
    }
    void init(const vector<vector<string>> &operators,
              const function<T(const string&, T, T)> operation) {
        OPERATORS = operators, OPERATION = operation;
    }
    void init(const vector<vector<string>> &operators,
              const function<T(const string&, T, T)> operation,
              const function<T(const string&, int&)> get_leaf) {
        OPERATORS = operators, OPERATION = operation;
        GET_LEAF = get_leaf;
    }
    void init(const vector<vector<string>> &operators,
              const function<T(const string&, T, T)> operation,
              const function<T(const string&, int&)> get_leaf,
              const vector<string> &unary_operators,
              const function<T(const string &op, T)> unary_operation) {
        OPERATORS = operators, OPERATION = operation;
        GET_LEAF = get_leaf;
        UNARY_OPERATORS = unary_operators, UNARY_OPERATION = unary_operation;
    }
    void clear() {
        S = "";
        vals.clear(), ops.clear(), left.clear(), right.clear(), ids.clear();
    }
    
    /* node generator */
    // value
    int new_leaf(T val, int &id) {
        vals.push_back(val);
        ops.push_back(OPERATOR_NUMBER);
        left.push_back(-1);
        right.push_back(-1);
        ids.push_back(id++);
        return (int)vals.size() - 1;
    }
    // FUNC(lp)
    int new_node_with_left(T val, const string &op, int lp) {
        vals.push_back(val);
        ops.push_back(op);
        left.push_back(lp);
        right.push_back(-1);
        ids.push_back(-1);
        return (int)vals.size() - 1;
    }
    // (lp) op (rp)
    int new_node_with_left_right(const string &op, int lp, int rp) {
        vals.push_back(OPERATION(op, vals[lp], vals[rp]));
        ops.push_back(op);
        left.push_back(lp);
        right.push_back(rp);
        ids.push_back(-1);
        return (int)vals.size() - 1;
    }
    
    /* main parser */
    T parse(const string &str, bool default_parse_numeric = true) {
        clear();
        S = str;
        int p = 0, id = 0;
        root = parse(p, id, default_parse_numeric);
        return vals[root];
    }
    int parse(int &p, int &id, bool default_parse_numeric, int depth = 0) {
        assert(p >= 0 && p < (int)S.size());
        string op;
        if (depth < (int)OPERATORS.size()) {
            // recursive descent
            int lp = parse(p, id, default_parse_numeric, depth + 1);
            bool update = false;
            do {
                update = false;
                if (is_in_the_operators(p, op,
                                        OPERATORS[(int)OPERATORS.size() - depth - 1])) {
                    int rp = parse(p, id, default_parse_numeric, depth + 1);
                    lp = new_node_with_left_right(op, lp, rp);
                    update = true;
                }
            } while (p < (int)S.size() && update);
            return lp;
        }
        else if (S[p] == '(') {
            return get_bracket(p, id, default_parse_numeric);
        }
        else if (default_parse_numeric && (S[p] == '-' || isdigit(S[p]))) {
            return get_number(p, id);
        }
        else if (is_in_the_operators(p, op, UNARY_OPERATORS)) {
            return get_unary_operation(p, id, op, default_parse_numeric);
        }
        else {
            return new_leaf(GET_LEAF(S, p), id);
        }
    }
    bool is_the_operator(int &p, const string &op) {
        if (op != "" && S.substr(p, op.size()) == op) {
            p += op.size();
            return true;
        }
        return false;
    }
    bool is_in_the_operators(int &p, string &res_op, const vector<string> &ops) {
        for (const auto &op : ops) {
            if (is_the_operator(p, op)) {
                res_op = op;
                return true;
            }
        }
        return false;
    }
    int get_number(int &p, int &id) {
        long long val = 0, sign = 1;
        if (S[p] == '-') sign = -1, ++p;
        while (p < (int)S.size() && isdigit(S[p])) {
            val = val * 10 + (int)(S[p++] - '0');
        }
        return new_leaf(T(val * sign), id);
    }
    int get_bracket(int &p, int &id, bool default_parse_numeric) {
        ++p;  // skip "("
        int lp = parse(p, id, default_parse_numeric, 0);
        ++p;  // skip ")"
        return lp;
    }
    int get_unary_operation(int &p, int &id, const string &op,
                            bool default_parse_numeric) {
        int lp;
        if (S[p] == '(') lp = get_bracket(p, id, default_parse_numeric);
        else lp = parse(p, id, default_parse_numeric, (int)OPERATORS.size());
        return new_node_with_left(UNARY_OPERATION(op, vals[lp]), op, lp);
    }
    
    /* dump */
    void dump() {
        dump_rec(root);
    }
    void dump_rec(int v, string space = "") {
        cout << space << v << ": (" << ops[v] << ", " << vals[v]
             << ") -> left: " << left[v] << ", right: " << right[v] << endl;
        if (left[v] != -1) dump_rec(left[v], space + "  ");
        if (right[v] != -1) dump_rec(right[v], space + "  ");
    }
};


int main() {
    vector<vector<string>> operators = {{"*"}, {"+", "-"}};
    auto operation = [&](const string &op, bigint a, bigint b) -> bigint {
        if (op == "+") return a + b;
        else if (op == "-") return a - b;
        else if (op == "*") return a * b;
        else return 0;
    };
    Parser<bigint> ps(operators, operation);
    
    int N;
    cin >> N;
    string S, news;
    cin >> S;
    int c = 0;
    for (char i: S) {
    	if (i == '-') c++;
    	else {
    		if (c % 2 == 1) {
    			news += '-';
    			c = 0;
    		}
    		news += i;
    	}
    }
    cout << ps.parse(news) << endl;
}
0