oj.uz

Submission #69977

# Submission time Handle Problem Language Result Execution time Memory
69977 2018-08-22T07:34:35 Z khohko parentrises (BOI18_parentrises) C++17
100 / 100
 838 ms 13208 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;


ll dp[2][405][805];
ll pas[400];
void slv1(){
	ll q,n;
	string s;
	string pas;
	cin>>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;

	}
}

int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	ios::sync_with_stdio(0);

	ll q,n;
	cin>>q;
	if(q==1){
		slv1();
		return 0;
	}
	dp[0][0][400]=1;
	ll N=1,P=0;
	for(int i=0; i<=300; i++){
		pas[i]=0;
		for(int j=0; j<=400; j++)
			for(int k=0; k<=800; k++)
				dp[N][j][k]=0;
		for(int j=0; j<=400; j++){
			for(int k=0; k<=800; k++){
				dp[P][j][k]%=MOD;
				if(k>=1)
				dp[N][j+2][min(399,k-1)]+=dp[P][j][k];
				if(j>=1)
				dp[N][j-1][k+2]+=dp[P][j][k];
				dp[P][j][k]%=MOD;
				//if(dp[P][j][k])
				//cout<<i<<" "<<j<<" "<<k<<" "<<dp[P][j][k]<<endl;
				if(k>=400)
					pas[i]+=dp[P][j][k];
			}
		}
		swap(N,P);
		pas[i]%=MOD;
	}
	cin>>q;
	while(q--){
		cin>>n;
		cout<<pas[n]<<endl;
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 648 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 648 KB Output is correct
6 Correct 3 ms 648 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 3 ms 648 KB Output is correct
9 Correct 3 ms 648 KB Output is correct
10 Correct 2 ms 648 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 648 KB Output is correct
6 Correct 3 ms 648 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 3 ms 648 KB Output is correct
9 Correct 3 ms 648 KB Output is correct
10 Correct 2 ms 648 KB Output is correct
11 Correct 4 ms 648 KB Output is correct
12 Correct 3 ms 648 KB Output is correct
13 Correct 3 ms 740 KB Output is correct
14 Correct 3 ms 740 KB Output is correct
15 Correct 3 ms 740 KB Output is correct
16 Correct 20 ms 868 KB Output is correct
17 Correct 6 ms 1572 KB Output is correct
18 Correct 4 ms 1572 KB Output is correct
19 Correct 6 ms 1572 KB Output is correct
20 Correct 6 ms 1964 KB Output is correct
21 Correct 137 ms 3068 KB Output is correct
22 Correct 35 ms 10272 KB Output is correct
23 Correct 21 ms 10272 KB Output is correct
24 Correct 28 ms 10272 KB Output is correct
25 Correct 46 ms 13208 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 13208 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 13208 KB Output is correct
2 Correct 838 ms 13208 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 13208 KB Output is correct
2 Correct 838 ms 13208 KB Output is correct
3 Correct 797 ms 13208 KB Output is correct