제출 #1247110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247110		JakobZorz	Homework (CEOI22_homework)	C++20	100 / 100	90 ms	77804 KiB

Main

#include<bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
const int MOD=1e9+7;

const int TYPE_Q=0;
const int TYPE_MIN=1;
const int TYPE_MAX=2;

struct Node{
    int ty;
    int ch1,ch2;
};

Node nodes[2000000];
int curr_node=0;

int alloc_node(){
    return curr_node++;
}

string s;
int n;

int parse(int&i){
    int node=alloc_node();
    if(s[i]=='?'){
        nodes[node].ty=TYPE_Q;
        i++;
        return node;
    }

    if(s[i+1]=='i'){
        nodes[node].ty=TYPE_MIN;
    }else{
        nodes[node].ty=TYPE_MAX;
    }
    i+=4; // min( ali max(
    nodes[node].ch1=parse(i);
    i++; // ,
    nodes[node].ch2=parse(i);
    i++; // )
    return node;
}

// node lahko zavzame vrednosti od L do vkljucno R. returna {L,R}
pair<int,int>get(int node){
    if(nodes[node].ty==TYPE_Q)
       return{1,n}; 
    auto[L1,R1]=get(nodes[node].ch1);
    auto[L2,R2]=get(nodes[node].ch2);
    int L,R;
    if(nodes[node].ty==TYPE_MIN){
        L=min(L1,L2);
        int r1=n-R1,r2=n-R2;
        R=n-r1-r2-1;
    }else{
        R=max(R1,R2);
        int l1=L1-1,l2=L2-1;
        L=2+l1+l2;
    }
    //cout<<"RET "<<L<<" "<<R<<"\n";
    return{L,R};
}

void solve(){
    cin>>s;
    n=0;
    for(char c:s)
        n+=c=='?';
    int idx=0;
    int root=parse(idx);
    auto res=get(root);
    cout<<res.second-res.first+1<<"\n";
}

int main(){
    ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

/*
 */

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