oj.uz

Submission #69976

# Submission time Handle Problem Language Result Execution time Memory
69976 2018-08-22T07:33:59 Z khohko parentrises (BOI18_parentrises) C++17
55 / 100
 1000 ms 5728 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);
	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;
	}
	ll q,n;
	cin>>q;
	if(q==1){
		slv1();
		return 0;
	}
	cin>>q;
	while(q--){
		cin>>n;
		cout<<pas[n]<<endl;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 924 ms 5368 KB Output is correct
2 Correct 866 ms 5608 KB Output is correct
3 Correct 896 ms 5640 KB Output is correct
4 Correct 927 ms 5640 KB Output is correct
5 Correct 804 ms 5640 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 856 ms 5640 KB Output is correct
2 Correct 727 ms 5656 KB Output is correct
3 Execution timed out 1020 ms 5660 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 856 ms 5640 KB Output is correct
2 Correct 727 ms 5656 KB Output is correct
3 Execution timed out 1020 ms 5660 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 856 ms 5640 KB Output is correct
2 Correct 727 ms 5656 KB Output is correct
3 Execution timed out 1020 ms 5660 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 932 ms 5728 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 932 ms 5728 KB Output is correct
2 Correct 868 ms 5728 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 932 ms 5728 KB Output is correct
2 Correct 868 ms 5728 KB Output is correct
3 Correct 764 ms 5728 KB Output is correct