제출 #1229868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229868		Muhammad_Aneeq	parentrises (BOI18_parentrises)	C++20	56 / 100	1095 ms	9176 KiB

parentrises

#include <iostream>
#include <vector>
using namespace std;
bool check(string s,string ans)
{
    int n=s.size();
    {
        int cnt=0;
        for (int i=0;i<n;i++)
        {
            if (ans[i]=='B') continue;
            cnt+=(s[i]=='('?1:-1);
            if (cnt<0)
                return 0;
        }
        if (cnt)
            return 0;
    }
    {
        int cnt=0;
        for (int i=0;i<n;i++)
        {
            if (ans[i]=='R') continue;
            cnt+=(s[i]=='('?1:-1);
            if (cnt<0)
                return 0;
        }
        if (cnt)
            return 0;
    }
    return 1;
}
int sb;
string sb1(string s)
{
    int n=s.size();
    vector<int>l,r;
    string ans(n,'G');
    for (int i=0;i<n;i++)
    {
        if (s[i]=='(')
            l.push_back(i);
        else
            r.push_back(i);
        if (r.size()>l.size())
        {
            if (l.size()==0)
                return "impossible";
            l.pop_back();
            ans[r.back()]='B';
            r.pop_back();
            ans[r.back()]='R';
            r.pop_back();
        }
    }
    while (l.size()>r.size())
    {
        if (r.size()==0)
            return "impossible";
        r.pop_back();
        ans[l.back()]='B';
        l.pop_back();
        ans[l.back()]='R';
        l.pop_back();
    }
    if (check(s,ans))
        return ans;
    return "impossible";
}
inline void solve()
{
    if (sb==1)
    {
        string s;
        cin>>s;
        cout<<sb1(s)<<endl;
        return;
    }
    int n;
    cin>>n;
    int ans=0;
    for (int i=0;i<(1<<n);i++)
    {
        string s(n,' ');
        for (int j=0;j<n;j++)
        {
            if ((1<<j)&i)
                s[j]='(';
            else
                s[j]=')';
        }
        ans+=(sb1(s)!="impossible");
    }
    cout<<ans<<endl;
}
int main()
{
	cin>>sb;
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    cin>>t;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 0 / 16
• Subtask 7: 0 / 28