QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#143239#6750. CalculateKidding_MaAC ✓1ms3588kbC++206.5kb2023-08-20 22:53:262023-08-20 22:53:28

Judging History

你现在查看的是最新测评结果

  • [2023-08-20 22:53:28]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3588kb
  • [2023-08-20 22:53:26]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using i128 = __int128;

namespace cpstd {
#define range(a) begin(a), end(a)

template <class T>
T max(const vector<T> &a) {
    return *std::max_element(a.begin(), a.end());
}

template <class T>
T min(const vector<T> &a) {
    return *std::min_element(a.begin(), a.end());
}

template <class T>
struct Fenwick {
    int n;
    std::vector<T> a;
    Fenwick(const int &n = 0) : n(n), a(n, T()) {}
    void modify(int i, T x) {
        for (i++; i <= n; i += i & -i) {
            a[i - 1] += x;
        }
    }
    T get(int i) {
        T res = T();
        for (; i > 0; i -= i & -i) {
            res += a[i - 1];
        }
        return res;
    }
    T sum(int l, int r) { // [l, r)
        return get(r) - get(l);
    }
    T kth(T k) {
        int x = 0;
        for (int i = 1 << std::__lg(n); i; i >>= 1) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};

template <class T>
T exgcd(T a, T b, T &x, T &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    T g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

template <class T>
T floor_sum(T n, T m, T a, T b) {
    T ans = 0;
    if (a < 0) {
        T a2 = (a % m + m) % m;
        ans -= n * (n - 1) / 2 * ((a2 - a) / m);
        a = a2;
    }
    if (b < 0) {
        T b2 = (b % m + m) % m;
        ans -= n * ((b2 - b) / m);
        b = b2;
    }
    while (1) {
        if (a >= m) {
            ans += n * (n - 1) / 2 * (a / m);
            a %= m;
        }
        if (b >= m) {
            ans += n * (b / m);
            b %= m;
        }
        T y_max = a * n + b;
        if (y_max < m) {
            break;
        }
        n = y_max / m;
        b = y_max % m;
        swap(m, a);
    }
    return ans;
}

template <class T, class U1, class U2>
T power(T a, U1 b, U2 p) {
    T res = 1;
    for (; b; b >>= 1, a = a * a % p) {
        if (b & 1) {
            res = res * a % p;
        }
    }
    return res;
}

template <class T, class U>
T power(T a, U b) {
    T res = 1;
    for (; b; b >>= 1, a = a * a) {
        if (b & 1) {
            res = res * a;
        }
    }
    return res;
}

__int128 abs(const __int128 &v) {
    return (v < 0 ? -v : v);
}

std::mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

istream &operator>>(istream &is, __int128 &v) {
    std::string s;
    is >> s;
    v = 0;
    for (auto &si : s) {
        v = v * 10 + si - '0';
    }
    return is;
}

ostream &operator<<(ostream &os, const __int128 &v) {
    if (v <= 1000000000000000000) {
        return os << (long long) (v);
    }
    return os << (long long) (v / 1000000000000000000) << std::setw(18) << std::setfill('0') << (long long) (v % 1000000000000000000);
}

template <class T>
T crt(const vector<T> &r, const vector<T> &m) {
    int n = r.size();
    T r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        T m1 = m[i];
        T r1 = r[i] % m1;
        if (r1 < 0) {
            r1 += m1;
        }
        if (m0 < m1) {
            std::swap(r0, r1);
            std::swap(m0, m1);
        }
        if (!(m0 % m1)) {
            if (r0 % m1 != r1) {
                return -1;
            }
            continue;
        }
        T x, y;
        T g = exgcd(m0, m1, x, y);
        if ((r1 - r0) % g) {
            return -1;
        }
        T u1 = m1 / g;
        r0 += (r1 - r0) / g % u1 * x % u1 * m0;
        m0 *= u1;
        if (r0 < 0) {
            r0 += m0;
        }
    }
    return r0;
}

constexpr int B = 777;
constexpr long long P = 100000000000031;

long long *p;

void initHash(int N) {
    p = new long long [N + 1];
    for (int i = 0; i <= N; i++) {
        p[i] = 0;
    }
    p[0] = 1;
    for (int i = 1; i <= N; i++) {
        p[i] = p[i - 1] * B % P;
    }
}

struct StringHash {
    std::vector<long long> h;
    StringHash() : h(1) {}
    void push_back(char ch) {
        h.push_back((h.back() * B + ch) % P);
    }
    long long get(int l, int r) { // [l, r)
        return (h[r] + __int128(h[l]) * (P - p[r - l])) % P;
    }
};

struct UnionFind {
    int n;
    std::vector<int> f, sz;
    UnionFind(const int &n = 0) : n(n), f(n), sz(n, 1) {
        std::iota(f.begin(), f.end(), 0);
    }
    int get(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x != y) {
            f[y] = x;
            sz[x] += sz[y];
            return 1;
        }
        return 0;
    }
    bool united(int x, int y) {
        return get(x) == get(y);
    }
    int size(int x) {
        x = get(x);
        return sz[x];
    }
};
}

using namespace cpstd;

void solve() {
    
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    
int N = s.size();
vector<array<i64, 3>> NUM;
vector<char> OP;
    
auto work = [&]() {
    char op = OP.back();
    OP.pop_back();
    auto [r, r1, r2] = NUM.back();
    NUM.pop_back();
    auto [l, l1, l2] = NUM.back();
    NUM.pop_back();
    if (op == '-') {
        NUM.push_back({l - r, l1 + r2, l2 + r1});
    }
    if (op == '+') {
        NUM.push_back({l + r, l1 + r1, l2 + r2});
    }
};
    
auto run = [&](string &s) {
    for (int i = 0; i < N; ) {
        if (s[i] == '?') {
            NUM.push_back({0, 1, 0});
            i++;
        } else if (isdigit(s[i])) {
            i64 res = 0;
            for ( ; i < N && isdigit(s[i]); i++) {
                res *= 10;
                res += s[i] - '0';
            }
            NUM.push_back({res, 0, 0});
        } else {
            if (s[i] == '(') {
                OP.push_back('(');
            } else if (s[i] == ')') {
                while (OP.back() != '(') {
                    work();
                }
                OP.pop_back();
            } else {
                while (!OP.empty() && OP.back() != '(') {
                    work();
                }
                OP.push_back(s[i]);
            }
            i++;
        }
    }
    while (!OP.empty()) {
        work();
    }
    auto [res, add, del] = NUM.back();
    NUM.pop_back();
    return res + 9 * add;
};
cout << run(s) << '\n';


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3532kb

input:

?+?

output:

18

result:

ok 1 number(s): "18"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

(?+9)-(?+1)

output:

17

result:

ok 1 number(s): "17"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

((9)-(((8)-(2))+(((1+(1))-(1+((2)+2+2)))+(5)+4))+(((7)-((9)+3))-((8)-(0-(2))+0))+((6)-(6+(((4)-(9))-(8-((9)+(1))+(0)))+(2-((9)+7))-(1)))-((((7)+(1))-((3)+(3)))-((2)-((6)-((3)-(8)))))+(2+0-((6)-(1))))-((((3)-(((0)+((4)-(9))+((6+8)+4)+(5)-(4-(3)-(8)))-((8)-(2))))+(((2)-(4))+(6)-(2))+(6-(1))-((2+9)-(3+...

output:

-63

result:

ok 1 number(s): "-63"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

(((((4)-((5)+(1))-(6-(8-(1))+((0)+(9))))+((2-(2))+(3+3-(((7)-(6))-(3))+(((3)+((5)-((0)-(6-(0)))))+((0)+((0)-(7)))+1-((3)-((8)-(8)))))))-(((((5-(3)-((((8)+0)+(9)-((7)-(9)))-(7)))+(2))+8+((4)-(6)+((5)-((7)+(2))))-(8-((7)+(3)+(9))))-(((9-(9-(8)))+1-((((4)+(9))+(8))+(2+(7)+3)))+((((6)+(2))-(1)-((((6+7-(...

output:

356

result:

ok 1 number(s): "356"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

((((((0+(5))+6)-((4)+(((7)+2)+6)-((((7)-(9))-(1))-((8-(2))+(5))-(2-((5)-(8))))-(3)))+((8)-(6)+3))+(7-(((4)+(6))+(((6)-(4))-(5))-(5-(4))-(5)+(2-(2)))+(6+(3+(2)+(7)+3)))+(((3)+(4)+(7)-(6-(5)))-((9+(8))+((1)-(0)))+((((8)+1)-(4))+(4))+(((4)-(4))+9+(((8)+3)-(6)+5)))-(((((5)+(9))-((3)-(0)))+((((0)+3)-(2))...

output:

-185

result:

ok 1 number(s): "-185"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

((((1-(4-(9)+((5)+(5)))+(((6)-(6)+((2)-(6)))-((7)+6)-(3)))-(2-((((7)+(8+(6)))-(5)+(7-((2)-(8)))+(4)-(((8)-(1))+(1)))-((3-(5)+(2-(1)))+2+(5)-(4))-(7)))+(9-(9+5)-(7)-((6)-(4)))+(((1+6)+(6+0-(9))+(((9+((2)+((1)-(5)))-(1))-(1))-(3+8-(2))))-((4)+((7)-(7))-(((2)-(6))+3)-((2-(3))+(4)-((0)-(1+(7)))+((0)+2))...

output:

-20

result:

ok 1 number(s): "-20"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

(((0-(((6)+(2))+4-(4)-(2))-((8)+4+(2))+2+(1+(9))+((2+(3))+(((8-(6))-(9))+(6)-((4)+0))-((7)-(3)-((3)+((3)+6-(2)))-(4))))-(((6)-((5)-(5-((9)+1-(6)))))+8)+(((8+(5)-(1))-(5))+(7-(0)-(0))+(((3)+(2)+(6)+0+(7)+(7)+(0+0-((1)+3)))-(((5+(8))-(9))-(8-((4)+9+(2)-(6-(6)-(4+5)))))+(2)-((((2)+1)+(0)+(3))+2))))-(((...

output:

200

result:

ok 1 number(s): "200"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

(8)+((7)+4)+(3)-(((3-(0)+(3+4)+(6-(6)+(7-((8+(8))-(7)+((5)-(6+2)))))-((8+(4))+((0)-((4)-(6)+(4)+((7+9)+(5+4-(5))))-(8))))-((5)+((2)-(6))+(5)))+(8+(((3)-(8))-(7)+(7-(0+(4-(1))-((7)+(0)+((7)-(1)))))))+(7-(5))+((((((2-(((3)+1)+(((2)+(5))+4)))+(((5)+4-(6))+(((2)+(2))-(4)-(4-(9))+((0)+(1))))+9-(8)+((6)+(...

output:

-24

result:

ok 1 number(s): "-24"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

(((9-(4-(9-(1)))+((8)-(1))+(5-(3+2)))+(((((((1)+0)+9)-(8))+(6-(4)-(0)))-(2+((((6)-(6)-(8))-((5)-(6)))-((7)+(1)))))+(((1-(8)+(9-((7)-(1)))+(0)-((4)-(0)))+1+(9)-((((6)-(1))-(7))-(6+3+8))-((1)+(1)-(9-(9))+8-(((9)-(5))+3-(9))+(3-((8)-(3))))+(3)-(0)-(2-(2-(8)))-(5+7)+(4)+(5)+(8+((6)-(2))+(3-(8))))-((0)-(...

output:

-69

result:

ok 1 number(s): "-69"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

((((((2+(((9)+(9))-(5)))+(0))+((2)-(5+8)-((((3)+(4))+9+((5-(((6)+(9))-(6)))-((8)+0)+(6)))+((4-(7))+(4)+(5-(1))+(4)-(4)+4))))-(((9)+((2)-(9))-(1)-(0-(3)+1))+(5)-((6-((9)+8))-(6-(4)))-(6))-(((((7)+8)-((3)+(0)-(1)-(((2)-(1))-(5))))+((2+(0))-((8)-((4)-(6))-((5)-(2))+(7))))-((8)-(9)-((8+(0-(0-(4)))+5)+(5...

output:

40

result:

ok 1 number(s): "40"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

(((((((0)-(0))-((((5)-((0)-(0)))+(((1)-(7+6))-((5)+0)))+3+7))-((4+4)-(6)-(9-(3+(1)))))-((((0)-(9)-(2))-((1-(2))-(5-(?))-((6)+(0)-(0))-(8+(9-(2)))))+(((7+4+(0)-((9)+8+(0+3+0)))-(2-(8+0)))-(0))))+(((((9)-(9))+((3+3+4)+(1)+(6)+((1)-(5))))-(3)-((6)+(5)))+(5)+4+1)+(((((((1)-(7))-((9)+(2)+1-(9+(4))))+(((4...

output:

-143

result:

ok 1 number(s): "-143"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

((((((8+(6))+(3)-(1)+((4-(8))+4)+(((9)-((0-(3))+(1))-(4))-((2-(6))-(((9-(3))+(1)-((7)-((1)+((2)-(2)))))+(2+(6-(8)))))+(2+(0)))+(5+9+((2+4-(0))-(((5)+(1+3)-(((7-(1))-(2))-(1)))-(9+((2)-(3)))))+(((7)-((5)+1+9-(1)))-((4)-(5-(0+5)-((8)-((5)+(0))-((8)+(0)-(4)-(0)))))))-(((3)+(0)+3)-(8-(0)+4)))+((1-(2)+((...

output:

52

result:

ok 1 number(s): "52"