Submission #848333

#	Time	Username	Problem	Language	Result	Execution time	Memory
848333		JakobZorz	Homework (CEOI22_homework)	C++14	13 / 100	125 ms	109264 KiB

Main

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
#include<limits.h>
#include<math.h>
#include<iomanip>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<cstring>
#include<sstream>

#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD=1e9+7;
typedef pair<ll,ll>point;
//#define x first
//#define y second

string str;
int n;
struct Node{
    Node*ch1=nullptr,*ch2=nullptr;
    bool q=false;
    bool is_max=false;
};

Node* parse(int&i){
    Node*result=new Node;
    
    if(str[i]=='?'){
        i++;
        n++;
        result->q=true;
        return result;
    }
    
    i++;
    result->is_max=str[i]=='a';
    i+=3;
    
    result->ch1=parse(i);
    i++;
    result->ch2=parse(i);
    i++;
    
    return result;
}

pair<int,int>get(Node*node){
    if(node->q)
        return{0,n};
    int l=0,r=0;
    auto res1=get(node->ch1);
    auto res2=get(node->ch2);
    if(node->is_max){
        l=max(res1.first,res2.first)+1;
        r=max(res1.second,res2.second);
    }else{
        l=min(res1.first,res2.first);
        r=min(res1.second,res2.second)-1;
    }
    
    return{l,r};
}

Node*root;

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    cin>>str;
    int index=0;
    root=parse(index);
    auto res=get(root);
    cout<<res.second-res.first<<"\n";
    
    return 0;
}

/*
 
 min(min(?,?),min(?,?))
 1
 
 max(?,max(?,min(?,?)))
 2
 
 min(max(?,?),min(?,max(?,?)))
 3
 
 
 */

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