oj.uz

Submission #848333

# Submission time Handle Problem Language Result Execution time Memory
848333 2023-09-12T06:53:24 Z JakobZorz Homework (CEOI22_homework) C++14
13 / 100
 125 ms 109264 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 109100 KB Output is correct
2 Correct 118 ms 109120 KB Output is correct
3 Correct 125 ms 109264 KB Output is correct
4 Correct 119 ms 109004 KB Output is correct
5 Correct 117 ms 107980 KB Output is correct
6 Correct 115 ms 108236 KB Output is correct
7 Correct 114 ms 108160 KB Output is correct
8 Correct 118 ms 108492 KB Output is correct
9 Correct 117 ms 108648 KB Output is correct
10 Correct 116 ms 107980 KB Output is correct
11 Correct 112 ms 108652 KB Output is correct
12 Correct 114 ms 109208 KB Output is correct
13 Correct 1 ms 344 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -