| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 856226 | 2023-10-02T20:12:16 Z | Benmath | parentrises (BOI18_parentrises) | C++14 | 0 ms | 0 KB |
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int p;
cin >> p;
int t;
cin >> t;
while(t--){
string s;
cin >> s;
int n = s.size();
char ans[n];
char ans1[n];
int n1 = 0;
int n2 = 0;
for(int i = 0; i < n; i++){
ans[i] = '?';
if(s[i] == '('){
n1 ++;
}else{
n2 ++;
}
}
int t2 = 0;
for (int x = 0; x <= n1; x++){
int y = x - (n2 - n1);
int x1 = x;
int y1 = y;
if(y1 >= 0){
int t1 = 0;
for(int i = 0; i < n; i++){
if(s[i] == '(' and x1 > 0){
ans[i] = 'G';
x1 --;
}
}
for(int i = n - 1; i >= 0; i--){
if(s[i] == ')' and y1 > 0){
ans[i] = 'G';
y1 --;
}
}
stack<int>s1;
int trenlijevi = 0;
int trendesni = 0;
stack<int>s2;
for(int i = 0; i < n; i++){
if(ans[i] == 'G'){
if(s[i] == '('){
s1.push(i);
s2.push(i);
}else{
if(s1.empty() or s2.empty()){
t1++;
}else{
s1.pop();
s2.pop();
}
}
}else{
if(s[i] == '('){
if(trenlijevi == 0){
s1.push(i);
ans[i] = 'B';
trenlijevi ++;
}else{
s2.push(i);
ans[i] = 'R';
trenlijevi = 0;
}
}else{
if(trendesni == 0){
if(s1.empty()){
t1++;
}else{
s1.pop();
ans[i] = 'B';
}
trendesni = 1;
}else{
if(s2.empty()){
t1++;
}else{
s2.pop();
ans[i] = 'R';
}
trendesni = 0;
}
}
}
}
if(!s1.empty() or !s2.empty()){
t1++;
}
if(t1 == 0){
for(int i = 0; i < n; i++){
ans1[i] = ans[i],
}
t2++;
}
}
}
if(t2>1){
int brojac = 0;
int inf = 1e9;
while(brojac<=inf){
brojac++;
}
}
if(t2 == 0){
cout<<"impossible"<<endl;
}else{
for(int i = 0; i < n; i++){
cout<<ans1[i];
}
cout<<endl;
}
}
}