Submission #703083

#	Time	Username	Problem	Language	Result	Execution time	Memory
703083		nianny	Homework (CEOI22_homework)	C++17	100 / 100	210 ms	30900 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] == 40) {
                data[cnt].s = (S[i - 2] == 97);
                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] == 63) {
                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] == 41) 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:26: 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:26: 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:34: 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:34: 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