Submission #1090591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090591		noyancanturk	parentrises (BOI18_parentrises)	C++17	50 / 100	96 ms	10060 KiB

parentrises

#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int lim=5e5+100;

void solve1(){
  string s;
  cin>>s;
  int n=s.size();
  int ty[n]{};
  int haveemp=0;
  vector<int>pools[2];
  for(int i=0;i<n;i++){
    if(s[i]=='('){
      haveemp++;
    }else if(1<haveemp){
      pools[0].pb(i);
      haveemp-=2;
    }else if(haveemp){
      pools[1].pb(i);
      ty[i]=1;
      haveemp=0;
    }else if(pools[0].size()){
      int toconvert=pools[0].back();
      pools[0].pop_back();
      ty[toconvert]=ty[i]=1;
      pools[1].pb(i);
      pools[1].pb(toconvert);
    }else if(pools[1].size()){
      int toconvert=pools[1].back();
      pools[1].pop_back();
      ty[i]=2;
      ty[toconvert]=3;
    }else{
      cout<<"impossible\n";
      return;
    }
  }
  if(haveemp){
    cout<<"impossible\n";
    return;
  }
  int needgreen=0,needred=0,needblue=0;
  string ans=string(n,' ');
  for(int i=n-1;0<=i;i--){
    if(s[i]=='('){
      if(needgreen){
        ans[i]='G';
        needgreen--;
      }else if(needred){
        ans[i]='R';
        needred--;
      }else if(needblue){
        ans[i]='B';
        needblue--;
      }
    }else if(ty[i]==0){
      ans[i]='G';
      needred++,needblue++;
    }else if(ty[i]==1){
      ans[i]='G';
      needgreen++;
    }else if(ty[i]==2){
      ans[i]='B';
    }else{
      ans[i]='R';
      needgreen++;
    }
  }
  cout<<ans<<"\n"; 
}
void solve2(){}

int main(){
  #ifdef Local
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
  #endif
  int _;
  cin>>_;
  if(_==1){
    int t;
    cin>>t;
    while(t--)solve1();
  }else{
    int t;
    cin>>t;
    while(t--)solve2();
  }
}

• 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