結果

問題 No.2031 Colored Brackets
コンテスト
ユーザー vjudge1
提出日時 2025-09-27 14:45:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,747 bytes
コンパイル時間 1,842 ms
コンパイル使用メモリ 178,836 KB
実行使用メモリ 15,944 KB
最終ジャッジ日時 2025-09-27 14:45:39
合計ジャッジ時間 5,686 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3 TLE * 1
other -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(!(c>='0'&&c<='9')){
		if(c=='-')	f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)	write(x/10);
	putchar(x%10+'0');
	return ;
}
string s;
int sum=0;
const int M=1000000007; 
void dfs(int now,int last,stack<int> st){//0 ? 1 ? 2? 
	if(now==s.size()){
		sum++;
		sum%=M; 
		return ;
	}
	if(last==0){
		if(s[now]==')'){
			if(!st.empty()){
				int x=st.top();
				st.pop();
				if(x==0){
					stack<int> a=st;
					a.push(1);
					dfs(now+1,1,a);
					a=st;
					a.push(2);
					dfs(now+1,2,a);
				}
				else{
					stack<int> a=st;
					a.push(0);
					dfs(now+1,0,a);
				}
			}
		}
		else{
			stack<int> a=st;
			a.push(0);
			dfs(now+1,0,a);
			a=st;
			a.push(1);
			dfs(now+1,1,a);
			a=st;
			a.push(2);
			dfs(now+1,2,a);
		}
	}
	if(last==1){
		if(s[now]==')'){
			if(!st.empty()){
				int x=st.top();
				st.pop();
				if(x==0){
					stack<int> a=st;
					a.push(2);
					dfs(now+1,2,a);
				}
				else{
					stack<int> a=st;
					a.push(0);
					dfs(now+1,0,a);
				}
			}
		}
		else{
			stack<int> a=st;
			a.push(0);
			dfs(now+1,0,a);
			a=st;
			a.push(2);
			dfs(now+1,2,a);
		}
	}
	if(last==2){
		if(s[now]==')'){
			if(!st.empty()){
				int x=st.top();
				st.pop();
				if(x==0){
					stack<int> a=st;
					a.push(1);
					dfs(now+1,1,a);
				}
				else{
					stack<int> a=st;
					a.push(0);
					dfs(now+1,0,a);
				}
			}
		}
		else{
			stack<int> a=st;
			a.push(1);
			dfs(now+1,1,a);
		}
	}
	return ;
}
signed main(){
	int n=read();
	cin>>s;
	stack<int> s;
	dfs(0,0,s);
	cout<<sum;
	return 0;
}
0