제출 #641352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
641352		andrei_boaca	Homework (CEOI22_homework)	C++14	53 / 100	26 ms	23900 KiB

Main

#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)
        {
            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;
    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.first<<' '<<x.second;
    cout<<x.second-x.first+1;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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