結果

問題 No.2595 Parsing Challenge
コンテスト
ユーザー fdironia
提出日時 2023-12-24 04:46:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 835 ms / 6,000 ms
コード長 11,680 bytes
コンパイル時間 3,199 ms
コンパイル使用メモリ 169,184 KB
実行使用メモリ 87,408 KB
最終ジャッジ日時 2024-09-27 13:36:23
合計ジャッジ時間 22,410 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>

#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;

using stc = stack<char>;
using sti = stack<int>;
using pbb = pair<bigint, bigint>;

struct node {
    char op;
    bigint a;
    int sz = 0;
    int l, r;

    node(const string &s) {
        a = bigint(s);
        l = r = -1;
    }

    node(char c) {
        op = c;
    }
};

using vn = vector<node>;

void proc(stc &so, sti &sn, vn &nodes) {
    char op = so.top();
    so.pop();
    if (op == '-') {
        op = '+';
        so.push('n');
        proc(so, sn, nodes);
    }

    int b = sn.top();
    sn.pop();
    int a;
    if (op == 'n') {
        nodes.emplace_back("-1");
        a = nodes.size() - 1;
        op = '*';
    } else {
        a = sn.top();
        sn.pop();
    }

    nodes.emplace_back(op);
    nodes.back().l = a;
    nodes.back().r = b;
    sn.push(nodes.size() - 1);
}

void dfs1(vn &nodes, int u) {
    if (nodes[u].l == -1) {
        nodes[u].sz = nodes[u].a.size();
        return;
    }

    dfs1(nodes, nodes[u].l);
    dfs1(nodes, nodes[u].r);

    if (nodes[nodes[u].l].sz < nodes[nodes[u].r].sz) {
        swap(nodes[u].l, nodes[u].r);
    }
    nodes[u].sz = nodes[nodes[u].l].sz + nodes[nodes[u].r].sz;
}

pbb dc(const vn &ops, int l, int r) {
    if (r - l == 1) {
        if (ops[l].op == '*') {
            return {ops[l].a, bigint(0)};
        } else {
            return {bigint(1), ops[l].a};
        }
    }

    int mid = (l + r) / 2;
    pbb a = dc(ops, l, mid), b = dc(ops, mid, r);
    return {a.first * b.first, a.first * b.second + a.second};
}

void calc(vn &nodes, int u) {
    if (nodes[u].l == -1) {
        return;
    }

    vn ops;
    int v = u;
    for (; nodes[v].l != -1; v = nodes[v].l) {
        ops.push_back(nodes[v]);
        swap(ops.back().a, nodes[nodes[v].r].a);
    }

    pbb t = dc(ops, 0, ops.size());
    nodes[u].a = t.first * nodes[v].a + t.second;
}

void dfs2(vn &nodes, int u) {
    if (nodes[u].l == -1) {
        return;
    }

    dfs2(nodes, nodes[u].r);
    calc(nodes, nodes[u].r);
    dfs2(nodes, nodes[u].l);
}

int main() {
    int n;
    cin >> n;
    string s;
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == '-' && (s.length() == 0 || (!isdigit(s.back()) && s.back() != ')'))) {
            c = 'n';
        }
        s += c;
    }

    stc so;
    sti sn;

    vn nodes;

    string cur;
    for (char c : s) {
        if (isdigit(c)) {
            cur += c;
        } else {
            if (cur != "") {
                nodes.emplace_back(cur);
                sn.push(nodes.size() - 1);
                cur = "";
            }

            if (c == '(') {
                so.push(c);
            } else if (c == ')') {
                while (!so.empty() && so.top() != '(') {
                    proc(so, sn, nodes);
                }
                so.pop();
            } else if (c == '*') {
                while (!so.empty() && (so.top() == '*' || so.top() == 'n')) {
                    proc(so, sn, nodes);
                }
                so.push(c);
            } else if (c == 'n') {
                so.push(c);
            } else {
                while (!so.empty() && so.top() != '(') {
                    proc(so, sn, nodes);
                }
                so.push(c);
            }
        }
    }

    if (cur != "") {
        nodes.emplace_back(cur);
        sn.push(nodes.size() - 1);
        cur = "";
    }
    while (!so.empty()) {
        proc(so, sn, nodes);
    }

    dfs1(nodes, nodes.size() - 1);
    dfs2(nodes, nodes.size() - 1);
    calc(nodes, nodes.size() - 1);
    
    cout << nodes.back().a << endl;

    return 0;
}
0