Submission #641357

#	Time	Username	Problem	Language	Result	Execution time	Memory
641357		andrei_boaca	Homework (CEOI22_homework)	C++14	100 / 100	284 ms	213796 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
stack<int> stiva;
vector<int> nr,poz;
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)
        {
            int val=cnt1+p2.second;
            if(x<=val)
                return 1;
            val=cnt2+p1.second;
            if(x<=val)
                return 1;
        }
        return 0;
    }
    else
    {
        int have=cnt1-p1.second+1;
        have+=cnt2-p2.second+1;
        if(cnt1+cnt2-x+1>=have)
            {
                int val=cnt1+cnt2-p2.first+1;
                if(cnt1+cnt2-val+1<=x)
                    return 1;
                val=cnt2+cnt1-p1.first+1;
                if(cnt1+cnt2-val+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;
    if(op=="max")
    {
        valmin=p1.first+p2.first;
        valmax=max(cnt1+p2.second,cnt2+p1.second);
    }
    if(op=="min")
    {
        int have=cnt1-p1.second+1;
        have+=cnt2-p2.second+1;
        valmax=cnt1+cnt2-have+1;
        int val=max(cnt1+cnt2-p2.first+1,cnt2+cnt1-p1.first+1);
        valmin=cnt1+cnt2-val+1;
    }
    return {valmin,valmax};
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    int lg=s.size();
    nr.resize(lg+5);
    poz.resize(lg+5);
    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.first<<' '<<x.second;
    cout<<x.second-x.first+1;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'pii solve(int, int)':
Main.cpp:79:9: warning: unused variable 'st' [-Wunused-variable]
   79 |     int st=1;
      |         ^~
Main.cpp:80:9: warning: unused variable 'dr' [-Wunused-variable]
   80 |     int dr=cnt;
      |         ^~
Main.cpp: In function 'int main()':
Main.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~

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