Submission #1229863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229863		Muhammad_Aneeq	parentrises (BOI18_parentrises)	C++20	50 / 100	23 ms	8152 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;
        }
        // cout<<cnt<<endl;
        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;
        }
        // cout<<cnt<<endl;
        if (cnt)
            return 0;
    }
    return 1;
}
inline void solve()
{
	string s;
	cin>>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)
            {
                cout<<"impossible\n";return;
            }
            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)
        {
            cout<<"impossible\n";return;
        }
        r.pop_back();
        ans[l.back()]='B';
        l.pop_back();
        ans[l.back()]='R';
        l.pop_back();
    }
    if (check(s,ans))
        cout<<ans<<endl;
    else
        cout<<"impossible\n";
}
int main()
{
	int sb;
	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: 0 / 6
• Subtask 6: 0 / 16
• Subtask 7: 0 / 28