Submission #84852

#	Time	Username	Problem	Language	Result	Execution time	Memory
84852		Pajaraja	parentrises (BOI18_parentrises)	C++17	50 / 100	186 ms	16260 KiB

parentrises

#include <bits/stdc++.h>
using namespace std;
string s;
int a[1000007],parc[1000007];
char c[1000007];
int main()
{
	int p;
	int t;
	cin>>p>>t;
	if(p==1)
	{
		while(t--)
		{
			cin>>s;
			int n=s.size(),sum=0,bs=0,rs=0;
			bool pr=false;
			for(int i=0;i<n;i++) a[i]=s[i]=='('?1:-1;
			for(int i=0;i<n;i++) sum+=a[i];
			parc[n]=0;
			for(int i=n-1;i>=0;i--) parc[i]=parc[i+1]+(1-a[i])/2;
			for(int i=0;i<n;i++) if(a[i]==1 && sum<parc[i]) {sum++; s[i]='G';}
			for(int i=n-1;i>=0;i--) if(a[i]==-1 && sum>0) {sum--; s[i]='G';}
			for(int i=0;i<n;i++)
			{
				if(s[i]=='G') {bs+=a[i]; rs+=a[i];}
				if(s[i]=='(')
				{
					if(bs<rs) {bs+=a[i]; s[i]='B';}
					else {rs+=a[i]; s[i]='R';}
				}
				if(s[i]==')')
				{
					if(bs>rs) {bs+=a[i]; s[i]='B';}
					else {rs+=a[i]; s[i]='R';}
				}
				if(bs<0 || rs<0) pr=true;
			}
			if(bs!=0 || rs!=0) pr=true;
			if(pr) cout<<"impossible"<<endl;
			else cout<<s<<endl;
		}
	}
	else cout<<"JBG";
}

• 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