Submission #870394

#	Time	Username	Problem	Language	Result	Execution time	Memory
870394		Alcabel	Homework (CEOI22_homework)	C++17	100 / 100	148 ms	186240 KiB

Main

#include <bits/stdc++.h>
using namespace std;

struct Cell {
    int l, r, cnt;
    Cell() {}
    Cell(int _l, int _r, int _cnt) {
        l = _l, r = _r, cnt = _cnt;
    }
    ~Cell() {}
};

void solve() {
    string s;
    cin >> s;
    vector<int> comma(s.size()), other(s.size()), stk;
    for (int i = 0; i < (int)s.size(); ++i) {
        // cerr << i << ' ';
        if (s[i] == '(') {
            // cerr << "(\n";
            stk.emplace_back(i);
        } else if (s[i] == ',') {
            // cerr << ",\n";
            assert(!stk.empty());
            comma[stk.back()] = i;
        } else if (s[i] == ')') {
            // cerr << ")\n";
            assert(!stk.empty());
            other[stk.back()] = i;
            stk.pop_back();
        }
    }
    auto parse = [&](auto self, int l, int r) -> Cell {
        // cerr << "l: " << l << ", r: " << r << '\n';
        if (l == r) {
            return Cell(0, 0, 1);
        }
        assert(r - l + 1 >= 8);
        Cell res;
        Cell resL = self(self, l + 4, comma[l + 3] - 1);
        Cell resR = self(self, comma[l + 3] + 1, other[l + 3] - 1);
        if (s[l + 2] == 'n') {
            // min
            res.l = min(resL.l, resR.l);
            res.r = resL.r + resR.r;
        } else {
            // max
            res.l = resL.l + resR.l + 1;
            res.r = max(resL.cnt + resR.r, resR.cnt + resL.r);
        }
        res.cnt = resL.cnt + resR.cnt;
        return res;
    };
    Cell ans = parse(parse, 0, (int)s.size() - 1);
    cout << ans.r - ans.l + 1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34