Submission #1186777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186777		user192837	Homework (CEOI22_homework)	C++17	100 / 100	92 ms	105276 KiB

Main

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

string s;
const int N = 7e6 + 76;
int n, ind[N], zap[N], cnt = 0;

ar <int, 2> rec(int l, int r) {
    if (l == r)
        return {1, cnt};
    int m = zap[l + 3];
    ar <int, 2> lef = rec(l + 4, m - 1);
    ar <int, 2> rg = rec(m + 1, r - 1);
    ar <int, 2> res;
    if (s[l + 2] == 'n') {
        res[0] = min(lef[0], rg[0]);
        res[1] = cnt - (cnt - lef[1]) - (cnt - rg[1]) - 1;
    } else {
        res[0] = lef[0] + rg[0];
        res[1] = max(lef[1], rg[1]);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> s;
    n = s.size();
    stack <int> st;
    for (int i = 0; i < n; i++) {
        if (s[i] == '?')
            ind[i] = ++cnt;
        if (s[i] == ',')
            zap[st.top()] = i;
        if (s[i] == '(')
            st.push(i);
        if (s[i] == ')')
            st.pop();
    }
    ar <int, 2> res = rec(0, n - 1);
    cout << res[1] - res[0] + 1;
}

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