Submission #1151459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151459		Issa	Homework (CEOI22_homework)	C++20	53 / 100	11 ms	8648 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 2e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e7 + 100;
const ll MOD = 1e9 + 7;
const int maxl = 16;
const ll P = 31;

string s;
int f[maxn];

tuple<int, int, int> calc(int l, int r){
    // cout << l << ' ' << r << endl;
    if(l == r) return {1, 1, 1};
    int mid;
    for(int i = 0;; i++){
        if(s[l+i] == ','){
            mid = l + i;
            break;
        } if(s[r-i] == ','){
            mid = r - i;
            break;
        }
    }
    auto [lcnt, lmn, lmx] = calc(l + 4, f[l + 4]);
    auto [rcnt, rmn, rmx] = calc(f[l + 4] + 2, f[f[l + 4] + 2]);
    if(s[l+1] == 'i'){
        return {lcnt + rcnt, min(lmn, rmn), lmx + rmx - 1};
    } else{
        return {lcnt + rcnt, lmn + rmn, 
        lcnt + rcnt - min(lcnt - lmx, rcnt - rmx)};
    }
}

void test(){
    cin >> s;
    for(int i = s.size()-1; i >= 0; i--){
        if(s[i] == '?') f[i] = i;
        else if(s[i] == 'm'){
            f[i] = f[f[i + 4] + 2] + 1;
        }
        // if(f[i] > i) cout << i << ' ' << f[i] << endl;
    }
    auto [cnt, mn, mx] = calc(0, s.size()-1);
    cout << mx - mn + 1 << endl;
} 

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while(t--) test();
}

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