Submission #682907

#	Time	Username	Problem	Language	Result	Execution time	Memory
682907		nutella	Homework (CEOI22_homework)	C++17	100 / 100	169 ms	170812 KiB

Main

// Virtual participation 10:40-15:40 17.01.2023

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int n = s.size();

    vector<int> stk;

    vector<int> bracket(n, -1), comma(n, -1);

    int cnt = count(s.begin(), s.end(), '?');

    for (int i = 0; i < n; ++i) {
        if (s[i] == ')') {
            int p = stk.back();
            stk.pop_back();

            bracket[p] = i, bracket[i] = p;

            if (s[i - 1] == ')') {
                comma[p] = comma[i] = bracket[i - 1] - 4;
            } else {
                if (s[p + 1] == 'm') {
                    assert(s[p + 1] == 'm');
                    comma[p] = comma[i] = bracket[p + 4] + 1;
                } else {
                    comma[p] = comma[i] = p + 2;
                }
            }
        } else if (s[i] == '(') {
            stk.push_back(i);
        }
    }

    function<pair<int, int>(int, int)> solve = [&](int l, int r) -> pair<int, int> {
        if (l == r) {
            assert(s[l] == '?');
            return {0, 0};
        } else {
            while (l < n && s[l] != '(') {
                l += 1;
            }
            assert(l < r);
            assert(bracket[l] == r);

            int mid = comma[l];

            auto L = solve(l + 1, mid - 1);
            auto R = solve(mid + 1, r - 1);

            if (s[l - 1] == 'x') { // -> max
                return {L.first + R.first + 1, min(L.second, R.second)};
            } else { // -> min
                return {min(L.first, R.first), L.second + R.second + 1};
            }
        }
    };

    auto ans = solve(0, n - 1);

    cout << cnt - ans.first - ans.second << '\n';


    return 0;
}

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