Submission #263613

#	Time	Username	Problem	Language	Result	Execution time	Memory
263613		TadijaSebez	parentrises (BOI18_parentrises)	C++11	100 / 100	270 ms	223736 KiB

parentrises

#include <bits/stdc++.h>
using namespace std;
const int N=305;
const int mod=1e9+7;
int dp[N][N*2][N*2];
const int H=1000050;
char s[H],ans[H];
int main(){
	int t;
	scanf("%i",&t);
	if(t==1){
		int q;
		scanf("%i",&q);
		while(q--){
			scanf("%s",s+1);
			int n=strlen(s+1);
			for(int i=1;i<=n;i++)ans[i]='B';
			int cnt=0;
			for(int i=1,bal=0;i<=n;i++){
				if(s[i]=='(')bal++;
				else bal--;
				if(bal<0){
					ans[i]='R';
					cnt++;
					bal=0;
				}
			}
			for(int i=1;i<=n;i++){
				if(cnt&&s[i]=='('){
					ans[i]='G';
					cnt--;
				}
			}
			cnt=0;
			for(int i=n,bal=0;i>=1;i--){
				if(s[i]==')')bal++;
				else bal--;
				if(bal<0){
					ans[i]='R';
					cnt++;
					bal=0;
				}
			}
			for(int i=n;i>=1;i--){
				if(cnt&&s[i]==')'){
					ans[i]='G';
					cnt--;
				}
			}
			bool ok=1;
			int b1=0,b2=0;
			for(int i=1;i<=n;i++){
				if(s[i]=='('){
					if(ans[i]=='G')b1++,b2++;
					else if(ans[i]=='B')b1++;
					else b2++;
				}
				else{
					if(ans[i]=='G')b1--,b2--;
					else if(ans[i]=='B')b1--;
					else b2--;
				}
				if(b1<0||b2<0)ok=0;
			}
			if(b1!=0||b2!=0)ok=0;
			if(ok){
				ans[n+1]=0;
				printf("%s\n",ans+1);
			}else printf("impossible\n");
		}
	}else{
		dp[0][0][0]=1;
		for(int i=0;i<N-1;i++){
			for(int j=0;j<=2*i;j++){
				for(int k=0;k<=2*i;k++){
					dp[i+1][j+2][k+1]+=dp[i][j][k];
					if(dp[i+1][j+2][k+1]>=mod)dp[i+1][j+2][k+1]-=mod;
					if(j>0){
						dp[i+1][j-1][max(k-2,0)]+=dp[i][j][k];
						if(dp[i+1][j-1][max(k-2,0)]>=mod)dp[i+1][j-1][max(k-2,0)]-=mod;
					}
				}
			}
		}
		int q;
		scanf("%i",&q);
		while(q--){
			int n,ans=0;
			scanf("%i",&n);
			for(int j=0;j<=n*2;j++){
				ans+=dp[n][j][0];
				if(ans>=mod)ans-=mod;
			}
			printf("%i\n",ans);
		}
	}
	return 0;
}

Compilation message (stderr)

parentrises.cpp: In function 'int main()':
parentrises.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |  scanf("%i",&t);
      |  ~~~~~^~~~~~~~~
parentrises.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |   scanf("%i",&q);
      |   ~~~~~^~~~~~~~~
parentrises.cpp:15:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |    scanf("%s",s+1);
      |    ~~~~~^~~~~~~~~~
parentrises.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |   scanf("%i",&q);
      |   ~~~~~^~~~~~~~~
parentrises.cpp:89:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |    scanf("%i",&n);
      |    ~~~~~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28