Submission #1307070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307070		simona1230	Homework (CEOI22_homework)	C++20	0 / 100	22 ms	17420 KiB

Main

#include <bits/stdc++.h>

using namespace std;
string s;
int a[200001];
vector<int> v[200001];
int num=0,g;
void build()
{
    stack<int> h;
    for(int i=0;i<s.size();i++)
    {
        int tp=0;
        if(s[i]=='m')
        {
            if(s[i+1]=='i')a[++num]=-1;
            else a[++num]=1;

            if(h.size())
                v[h.top()].push_back(num);
            h.push(num);
        }

        if(s[i]==')')
            h.pop();

        if(s[i]=='?')
        {
            num++;
            g++;
            v[h.top()].push_back(num);
        }
    }

    /*for(int i=1;i<=num;i++)
    {
        cout<<i<<": ";
        for(auto j:v[i])
            cout<<j<<" ";
                cout<<endl;
    }*/
}

int cnt[200001];
int dp[1024][100001];
vector<int> p[100001];

void prec()
{
    for(int i=0;i<(1<<g);i++)
    {
        p[__builtin_popcount(i)].push_back(i);
    }
}

void dfs(int i)
{
    for(auto j:v[i])
    {
        dfs(j);
        cnt[i]+=cnt[j];
    }

    if(v[i].size())
    {
        int v1=v[i][0];
        int v2=v[i][1];

        for(auto b1:p[cnt[v1]])
        {
            for(auto b2:p[cnt[v2]])
            {
                if(b1&b2)continue;
                int b=b1+b2;

                int curr=(dp[v1][b1]|dp[v2][b2]);
                if(a[i]==-1)
                {
                    for(int j=g;j>=0;j--)
                    {
                        if(curr&(1<<j))
                        {
                            curr-=(1<<j);
                            break;
                        }
                    }
                }
                else
                {
                    for(int j=0;j<=g;j++)
                    {
                        if(curr&(1<<j))
                        {
                            curr-=(1<<j);
                            break;
                        }
                    }
                }

                dp[i][b]|=curr;
            }
        }
    }
    else
    {
        cnt[i]=1;
        for(int j=0;j<g;j++)
            dp[i][(1<<j)]=(1<<j);
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>s;
	build();
	prec();
	dfs(1);

	/*for(int i=1;i<=num;i++)
    {
        for(auto j:p[cnt[i]])
            cout<<i<<" "<<j<<" : "<<dp[i][j]<<endl;
    }*/
	cout<<__builtin_popcount(dp[1][(1<<g)-1])<<endl;
	return 0;
}

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