Submission #971263

#	Time	Username	Problem	Language	Result	Execution time	Memory
971263		vjudge1	Homework (CEOI22_homework)	C++17	100 / 100	276 ms	170912 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using bm = vector<bool>;
using ii = pair<int,int>;

int main() {
    string s;
    cin >> s;
    int n = 0, m = 0;
    vector<array<int, 2> > Fii;
    vector<int> Tip;/// -1 -> min; 0 -> valoare; 1 -> maxim
    int ultp = 0;
    function<int(int)> parse = [&](int poz) -> int {
        /// va crea un nod cu expresia care incepe la poz
        while(s[poz] == ',' || s[poz] == '(' || s[poz] == ')') ++poz;
        ultp = max(ultp, poz);
        ++n;
        if(s[poz] == '?') {
            ++m;
            Fii.push_back({-1, -1});
            Tip.emplace_back(0);
            return int(Tip.size()) - 1;
        }
        int f1 = parse(poz + 4), f2 = parse(ultp + 1);
        if(s[poz + 1] == 'i') Tip.emplace_back(-1);
        else Tip.emplace_back(1);
        Fii.push_back({f1, f2});
        return int(Tip.size()) - 1;
    };
    int rad = parse(0);

    struct nod {
        int len, st, dr;
    };

    auto fmin = [&](nod a, nod b) {
        return nod{a.len + b.len, min(a.st, b.st), a.dr + b.dr};
    };

    auto fmax = [&](nod a, nod b) {
        nod aa{a.len, a.len - a.dr - 1, a.len - a.st - 1};
        nod bb{b.len, b.len - b.dr - 1, b.len - b.st - 1};
        nod rr = fmin(aa, bb);
        nod r{rr.len, rr.len - rr.dr - 1, rr.len - rr.st - 1};
        return r;
    };


    function<nod(int)> eval = [&](int u) -> nod {
        if(Tip[u] == 0) {
            return nod{1, 0, 0};
        }
        auto v1 = eval(Fii[u][0]), v2 = eval(Fii[u][1]);
        if(Tip[u] == -1) return fmin(v1, v2);
        return fmax(v1, v2);
    };

    auto re = eval(rad);
    cout << re.dr - re.st + 1 << "\n";
    return 0;
}

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