Submission #667602

#	Time	Username	Problem	Language	Result	Execution time	Memory
667602		Lobo	Homework (CEOI22_homework)	C++17	100 / 100	192 ms	202300 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = -1;

vector<int> rs;
string s;
pair<int,pair<int,int>> sol(int l, int r) {
    if(l == r) {
        return mp(1,mp(1,1));
    }
    int l1 = -1;
    for(int i = l+1;;i++) {
        if(rs[i] != -1) {
            l1 = i;
            break;
        }
    }
    int r1 = rs[l1];
    auto aux1 = sol(l1,r1);
    int sz1 = aux1.fr;
    int mn1 = aux1.sc.fr;
    int mx1 = aux1.sc.sc;


    int l2 = -1;
    for(int i = r1+1;;i++) {
        if(rs[i] != -1) {
            l2 = i;
            break;
        }
    }
    int r2 = rs[l2];
    auto aux2 = sol(l2,r2);
    int sz2 = aux2.fr;
    int mn2 = aux2.sc.fr;
    int mx2 = aux2.sc.sc;

    int sz = sz1+sz2;
    int mn,mx;
    if(s[l-1] == 'n') {
        mn = min(mn1,mn2);
        mx = mx1+mx2;
    }
    else {
        mn = mn1+mn2;
        mx = min(mx1,mx2);
    }
    return mp(sz,mp(mn,mx));
    return mp(0,mp(0,0));
}
void solve() {
    cin >> s;

    stack<int> ls;
    for(int i = 0; i < s.size(); i++) {
        rs.pb(-1);
        if(s[i] == '(') {
            ls.push(i);
        }
        else if(s[i] == ')') {
            rs[ls.top()] = i;
            ls.pop();
        }
        else if(s[i] == '?') {
            rs[i] = i;
        }
    }

    for(int i = 0; i < s.size(); i++) {
        if(rs[i] != -1) {
            // cout << i << " " << rs[i] << endl;
        }
    }

    int l = -1;
    for(int i = 0;; i++) {
        if(rs[i] != -1) {
            l = i;
            break;
        }
    }
    auto aux = sol(l,s.size()-1);
    int sz = aux.fr;
    int mn = aux.sc.fr;
    int mx = aux.sc.sc;
    cout << sz-(mn-1)-(mx-1) << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:65:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
Main.cpp:79:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~

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