Submission #1255663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255663		Bahamin	Homework (CEOI22_homework)	C++20	100 / 100	100 ms	97472 KiB

Main

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e7 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

int match[MAX_N];
string s;
int n;

pair<pair<int, int>, pair<int, int>> f(int l)
{
    if (s[l] == '?') return make_pair(make_pair(1, 1), make_pair(l, 1));
    int ind = match[l + 3];
    auto x = f(l + 4);
    auto y = f(x.second.first + 2);
    pair<int, int> re;
    if (s[l + 1] == 'a') re.first = x.first.first + y.first.first, re.second = x.second.second + y.second.second - min(x.second.second - x.first.second, y.second.second - y.first.second);
    else re.first = min(x.first.first, y.first.first), re.second = x.first.second + y.first.second - 1;
    return make_pair(re, make_pair(ind, x.second.second + y.second.second)); 
}

void solve() {
    cin >> s;
    n = s.size();
    vector<int> open;
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == ')') open.push_back(i);
        else if (s[i] == '(') match[i] = open.back(), open.pop_back();
    }
    auto x = f(0);
    cout << x.first.second - x.first.first + 1 << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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