oj.uz

Submission #69964

# Submission time Handle Problem Language Result Execution time Memory
69964 2018-08-22T06:58:26 Z khohko parentrises (BOI18_parentrises) C++17
50 / 100
 161 ms 13336 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e12+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e5+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;


int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	ios::sync_with_stdio(0);
	ll q,n;
	string s;
	string pas;
	cin>>q>>q;
	while(q--){
		cin>>s;
		pas=s;
		n=s.size();
		for(int i=0; i<n; i++)pas[i]='G';
		stack<ll> sk;
		ll ca=0,cb=0,cr=0;
		bool e=1;
		for(int i=0; i<n; i++){
			if(s[i]=='(')ca++;
			else cb++;
			if(2*ca<cb){e=0;break;}
			if(s[i]==')'){
				cr++;
				if(cr>ca){
					cr--;
					pas[i]='R';
					pas[sk.top()]='B';
					sk.pop();
				}
				else sk.push(i);
			}
		}
		ca=cb=cr=0;
		while(sk.size())sk.pop();
		for(int i=n-1; i>=0; i--){
			if(s[i]=='(')ca++;
			else cb++;
			if(2*cb<ca){e=0;break;}
			if(s[i]=='('){
				cr++;
				if(cr>cb){
					cr--;
					pas[i]='B';
					pas[sk.top()]='R';
					sk.pop();
				}
				else sk.push(i);
			}
		}
		//cout<<e<<endl;
		if(!e)cout<<"impossible"<<endl;
		else cout<<pas<<endl;

	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 4 ms 360 KB Output is correct
3 Correct 3 ms 400 KB Output is correct
4 Correct 3 ms 452 KB Output is correct
5 Correct 3 ms 456 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 696 KB Output is correct
2 Correct 3 ms 752 KB Output is correct
3 Correct 3 ms 752 KB Output is correct
4 Correct 3 ms 752 KB Output is correct
5 Correct 3 ms 752 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 696 KB Output is correct
2 Correct 3 ms 752 KB Output is correct
3 Correct 3 ms 752 KB Output is correct
4 Correct 3 ms 752 KB Output is correct
5 Correct 3 ms 752 KB Output is correct
6 Correct 3 ms 824 KB Output is correct
7 Correct 3 ms 884 KB Output is correct
8 Correct 3 ms 884 KB Output is correct
9 Correct 4 ms 884 KB Output is correct
10 Correct 3 ms 884 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 696 KB Output is correct
2 Correct 3 ms 752 KB Output is correct
3 Correct 3 ms 752 KB Output is correct
4 Correct 3 ms 752 KB Output is correct
5 Correct 3 ms 752 KB Output is correct
6 Correct 3 ms 824 KB Output is correct
7 Correct 3 ms 884 KB Output is correct
8 Correct 3 ms 884 KB Output is correct
9 Correct 4 ms 884 KB Output is correct
10 Correct 3 ms 884 KB Output is correct
11 Correct 4 ms 884 KB Output is correct
12 Correct 3 ms 884 KB Output is correct
13 Correct 3 ms 884 KB Output is correct
14 Correct 4 ms 884 KB Output is correct
15 Correct 3 ms 884 KB Output is correct
16 Correct 22 ms 996 KB Output is correct
17 Correct 8 ms 1700 KB Output is correct
18 Correct 6 ms 1700 KB Output is correct
19 Correct 7 ms 1700 KB Output is correct
20 Correct 7 ms 2012 KB Output is correct
21 Correct 161 ms 3096 KB Output is correct
22 Correct 38 ms 10560 KB Output is correct
23 Correct 24 ms 10560 KB Output is correct
24 Correct 30 ms 10560 KB Output is correct
25 Correct 40 ms 13336 KB Output is correct

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 13336 KB Expected integer, but "impossible" found

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 13336 KB Expected integer, but "impossible" found

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 13336 KB Expected integer, but "impossible" found