oj.uz

Submission #641342

# Submission time Handle Problem Language Result Execution time Memory
641342 2022-09-16T13:43:08 Z andrei_boaca Homework (CEOI22_homework) C++14
0 / 100
 38 ms 28724 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
stack<int> stiva;
int nr[1000005];
int poz[1000005];
string s;
bool possible(string op,int cnt1,int cnt2, pii p1, pii p2,int x)
{
    if(op=="max")
    {
        if(p1.first+p2.first<=x)
            return 1;
        return 0;
    }
    else
    {
        int have=cnt1-p1.second+1;
        have+=cnt2-p2.second+1;
        if(cnt1+cnt2-have+1>=x)
            return 1;
        return 0;
    }
}
pii solve(int l,int r)
{
    int initl=l,initr=r;
    if(r-l+1<3)
        return {1,1};
    string op;
    for(int i=l;i<l+3;i++)
        op.push_back(s[i]);
    l=l+3;
    pii p1,p2;
    int cnt1=0,cnt2=0;
    if(isalpha(s[l+1]))
    {
        int lft=l+1;
        int rgt=poz[l+4];
        p1=solve(lft,rgt);
        cnt1=nr[rgt];
        if(lft>0)
            cnt1-=nr[lft-1];
        l=rgt+2;
    }
    else
    {
        int lft=l+1;
        int rgt=l+1;
        p1=solve(lft,rgt);
        cnt1=nr[rgt];
        if(lft>0)
            cnt1-=nr[lft-1];
        l=rgt+2;
    }
    int lft=l;
    int rgt=r-1;
    p2=solve(lft,rgt);
    cnt2=nr[rgt];
    if(lft>0)
        cnt2-=nr[lft-1];
    int cnt=nr[initr];
    if(initl>0)
        cnt-=nr[initl-1];
    int st=1;
    int dr=cnt;
    int valmin=1e9,valmax=0;
    for(int i=st;i<=dr;i++)
        if(possible(op,cnt1,cnt2,p1,p2,i))
        {
            valmin=min(valmin,i);
            valmax=max(valmax,i);
        }
    return {valmin,valmax};
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='(')
        {
            stiva.push(i);
        }
        if(s[i]==')')
        {
            int p=stiva.top();
            poz[p]=i;
            stiva.pop();
        }
        if(i>0)
            nr[i]=nr[i-1];
        nr[i]+=(s[i]=='?');
    }
    pii x=solve(0,s.size()-1);
    cout<<x.second-x.first+1;
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 28724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 34.0

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