| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 84850 | 2018-11-17T13:23:27 Z | Pajaraja | parentrises (BOI18_parentrises) | C++17 | 0 ms | 0 KB |
#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";
}