Submission #703084

#	Time	Username	Problem	Language	Result	Execution time	Memory
703084		nianny	Homework (CEOI22_homework)	C++17	100 / 100	223 ms	30924 KiB

Main

        #include <bits/stdc++.h>
        using namespace std;
        #define f first
        #define s second
        #define MP make_pair
        int main() {
            int N = 0; string S; cin >> S;
            for(int i = 0; i < S.size(); i++) if(S[i] == '?') N++;
            pair<pair<int,int>,bool> data[N - 1]; pair<int,int> value[N];
            for(int i = 0; i < N - 1; i++) {
                data[i].f.f = -1;
                data[i].f.s = -1;
            }
            value[N - 1] = make_pair(1, N);
            int cnt = 0; stack<int> st;
            for(int i = 0; i < S.size(); i++) {
                if(S[i] == '(') {
                    data[cnt].s = (S[i - 2] == 'a');
                    if(cnt != 0) {
                        if(data[st.top()].f.f == -1) data[st.top()].f.f = cnt;
                        else data[st.top()].f.s = cnt;
                    }
                    st.push(cnt);
                    cnt++;
                } else if(S[i] == '?') {
                    if(data[st.top()].f.f == -1) data[st.top()].f.f = N - 1;
                    else data[st.top()].f.s = N - 1;
                } else if(S[i] == ')') st.pop();
            }
            for(int i = N - 2; i >= 0; i--) {
                if(data[i].s == false) {
                    value[i].f = min(value[data[i].f.f].f, value[data[i].f.s].f);
                    value[i].s = value[data[i].f.f].s + value[data[i].f.s].s - (N + 1);
                } else {
                    value[i].f = value[data[i].f.f].f + value[data[i].f.s].f;
                    value[i].s = max(value[data[i].f.f].s, value[data[i].f.s].s);
                }
            }
            cout << value[0].second - value[0].first + 1;
        }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:8:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |             for(int i = 0; i < S.size(); i++) if(S[i] == '?') N++;
      |                            ~~^~~~~~~~~~
Main.cpp:16:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |             for(int i = 0; i < S.size(); i++) {
      |                            ~~^~~~~~~~~~
Main.cpp:9:38: warning: argument to variable-length array is too large [-Wvla-larger-than=]
    9 |             pair<pair<int,int>,bool> data[N - 1]; pair<int,int> value[N];
      |                                      ^~~~
Main.cpp:9:38: note: limit is 9223372036854775807 bytes, but argument is 18446744073709551604

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