Submission #851784

#	Time	Username	Problem	Language	Result	Execution time	Memory
851784		Andrei	Homework (CEOI22_homework)	C++17	53 / 100	144 ms	39008 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int n;

string s;

vector <int> posbrackets;

stack <int> stk;

int partner[1000005];

struct S
{
    int sz;
    int l,r;
    S(int _sz,int _l,int _r)
    {
        sz=_sz;
        l=_l;
        r=_r;
    }
};

S Merge(S A,S B,int type)
{
    S ans(0,0,0);

    ans.sz=A.sz+B.sz;

    if(type==0)
    {
        ans.l=min(A.l,B.l);
        ans.r=(A.sz+B.sz)-(A.sz-A.r)+1-(B.sz-B.r+1)-1;
    }
    else
    {
        ans.l=(A.l-1)+B.l+1;
        ans.r=(A.sz+B.sz)-min(A.sz-A.r,B.sz-B.r);
    }

    return ans;
}

S solve(int l,int r)
{
    S A(1,1,1),B(1,1,1);

    if(s[posbrackets[l]+1]=='m')
        A=solve(l+1,partner[l+1]);
    if(s[posbrackets[r]-1]==')')
        B=solve(partner[r-1],r-1);

    if(s[posbrackets[l]-1]=='x')
        return Merge(A,B,1);
    return Merge(A,B,0);
}

int main()
{
    cin>>s;
    n=(int)s.size();
    for(int i=0; i<n; i++)
        if(s[i]=='(' || s[i]==')')
            posbrackets.push_back(i);

    if(posbrackets.empty())
    {
        cout<<"1\n";
        return 0;
    }

    for(int i=0; i<(int)posbrackets.size(); i++)
    {
        int p=posbrackets[i];
        if(s[p]=='(')
            stk.push(i);
        else
        {
            partner[stk.top()]=i;
            partner[i]=stk.top();
            stk.pop();
        }
    }

    S ans=solve(0,(int)posbrackets.size()-1);

    cout<<ans.r-ans.l+1<<"\n";
    return 0;
}

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