제출 #1351252

#제출 시각아이디문제언어결과실행 시간메모리
1351252CyanberryHomework (CEOI22_homework)C++20
0 / 100
125 ms163844 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct oper;

struct oper {
    int id, type, subsize;
    oper* left = nullptr;
    oper* right = nullptr;
    oper(int d, int t) {
        id = d;
        type = t;
        subsize = t == 0;
    }
    oper* assign(oper* lol) {
        if (left == nullptr) {
            left = lol;
            return left;
        } else {
            right = lol;
            return right;
        }
    }
};

int split;

void dfs(oper* curr) {
    // cout<<(curr->id)<<'\n';
    // cout.flush();
    if (curr->type == 0) return;
    dfs(curr->left);
    dfs(curr->right);
    if (curr->type == split) {
        curr->subsize = curr->left->subsize + curr->right->subsize;
    } else {
        curr->subsize = min(curr->left->subsize, curr->right->subsize);
    }
    
}

void reset(oper* curr) {
    // cout<<(curr->id)<<'\n';
    // cout.flush();
    if (curr->type == 0) {
        curr->subsize = 1;
    } else {
        curr->subsize = 0;
        if (curr->right == nullptr) {
            cout<<"WTF\n";
        } else {
            // cout<<'i'<<(curr->left->id)<<endl;
            // cout.flush();
            // cout<<'i'<<(curr->right->id)<<endl;
            // cout.flush();
            reset(curr->left);
            reset(curr->right);
        }
        
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N = 0;
    string arson;
    cin>>arson;
    oper* root = nullptr;
    oper* curr = nullptr;
    oper* junk = nullptr;
    stack<oper> ord;
    for (int i = 0; i < arson.size(); ++i) {
        // cout<<arson[i];
        // cout.flush();
        if (arson[i] == 'x') { //max
            if (root == nullptr) {
                root = new oper(i, 1);
                curr = root;
            } else {
                // cout<<(curr->id)<<endl;
                curr = curr->assign(new oper(i, 1));
            }
            ord.push(*curr);
        } else if (arson[i] == 'n') { //min
            if (root == nullptr) {
                root = new oper(i, 2);
                curr = root;
            } else {
                // cout<<(curr->id)<<endl;
                curr = curr->assign(new oper(i, 2));
            }
            ord.push(*curr);
        } else if (arson[i] == '?') {
            ++N;
            if (root == nullptr) break;
            // cout<<(curr->id)<<endl;
            curr->assign(new oper(i, 0));
        } else continue;
        
        while (!ord.empty() && curr->left != nullptr && curr->right != nullptr) {
            *curr = ord.top();
            ord.pop();
        }
        
    }
    if (N == 1) {
        cout<<"1";
    } else {
        // cout<<"MARK 1\n";
        reset(root);
        split = 1;
        // cout<<"MARK 2\n";
        dfs(root);
        int maxval = root->subsize;
        // cout<<maxval<<' ';
        // cout<<"MARK 3\n";
        reset(root);
        split = 2;
        // cout<<"MARK 4\n";
        dfs(root);
        // cout<<"MARK 5\n";
        int minval = root->subsize;
        maxval = N - maxval;
        
        cout<<(abs(maxval - minval));
    }
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...