QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#100496	#122. Security Gate	xiaoyaowudi	100 ✓	331ms	470176kb	C++17	3.8kb	2023-04-26 16:52:46	2023-04-26 16:52:47

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-04-26 16:52:47]
评测

测评结果：100
用时：331ms
内存：470176kb

查看

[2023-04-26 16:52:46]
提交

answer

#include <iostream>
#include <algorithm>
#include <cstring>
constexpr int p(1e9+7),N(310);
int n;char s[N];
void W(int &a,int b){a+=b;if(a>=p) a-=p;}
int W(int k){return k>=p?k-p:k;}
int solve()
{
	static int g[N][N][N],G[N][N][N];
	std::memset(g,0,sizeof(g));
	std::memset(G,0,sizeof(G));
	g[n+1][0][0]=1;
	for(int i(n);i>=1;--i)
	{
		for(int j((n-i+1)/2);j<=n-i;++j)
		{
			for(int t(0);t<=j;++t)
			{
				if(g[i+1][j][t])
				{
					int c(2*j-(n-i));
					W(G[i+1][j][c],g[i+1][j][t]);
					if(s[i]!='(')
					{
						W(g[i][j+1][std::max(c+1,t)],g[i+1][j][t]);
					}
					if(s[i]!=')' && c!=0)
					{
						W(g[i][j][t],g[i+1][j][t]);
					}
				}
			}
		}
	}
	for(int i(n);i>=1;--i)
	{
		for(int j((n-i+1)/2);j<=n-i;++j)
		{
			for(int t(0);t<=j;++t)
			{
				if(G[i+1][j][t])
				{
					int c(2*j-(n-i));
					if(s[i]!='(' && c+1<=2*t)
					{
						W(G[i][j+1][t],G[i+1][j][t]);
					}
					if(s[i]!=')' && c-1>t)
					{
						W(G[i][j][t],G[i+1][j][t]);
					}
				}
			}
		}
	}
	static int l[N][N][N],L[N][N][N];
	std::memset(l,0,sizeof(l));
	std::memset(L,0,sizeof(L));
	l[0][0][0]=1;
	for(int i(1);i<=n;++i)
	{
		for(int j(0);j<i;++j)
		{
			for(int t(0);t<=j;++t)
			{
				int c(2*j-(i-1));
				if(l[i-1][j][t])
				{
					if(s[i]!='(')
					{
						if(c>0) W(l[i][j][t],l[i-1][j][t]);
						else W(L[i][j][t],l[i-1][j][t]);
					}
					if(s[i]!=')')
					{
						W(l[i][j+1][std::max(t,c+1)],l[i-1][j][t]);
					}
				}
				if(L[i-1][j][t])
				{
					if(s[i]!='(')
					{
						W(L[i][j][t],L[i-1][j][t]);
					}
					if(s[i]!=')' && c+1<=2*t)
					{
						W(L[i][j+1][t],L[i-1][j][t]);
					}
				}
			}
		}
	}
	int ans(0);
	for(int i(0);i<=n;++i) W(ans,l[n][n/2][i]);
	for(int i(1);i<=n;i+=2) if(s[i]!='(')
	{
		static int b[N<<1];std::memset(b,0,sizeof(b));
		for(int j(0);j*2<i;++j) b[j]=l[i-1][i/2][j];
		for(int j(i/2);j>=0;--j) W(b[j],b[j+1]);
		for(int j((n-i+1)/2);j<=n-i;++j)
		{
			for(int t(0);t<=j;++t)
			{
				int k((2*j-(n-i)+1)/2);
				if(t>=k && t<2*k)
				{
					ans=(ans+2ll*G[i+1][j][t]*l[i-1][i/2][t-k])%p;
				}
				int lim(k);
				ans=(ans+2ll*g[i+1][j][t]*b[lim])%p;
			}
		}
	}
	for(int i(2);i<=n;i+=2) if(s[i]!=')')
	{
		for(int j(0);j<i;++j) if(2*j-(i-1)+1<=0)
		{
			static int b[N<<1];
			int l((n-i)/2),k((i-2-2*j)/2);
			for(int t(0);t<=l;++t) b[t]=g[i+1][l][t];
			for(int t(l);t>=0;--t) W(b[t],b[t+1]);
			int cur(0);
			for(int t(0);t<=j;++t) cur=(cur+1ll*L[i-1][j][t]*b[t+k])%p;
			std::memset(b,0,sizeof(int)*(l+1));
			if(2*j-(i-1)+1<0) W(ans,W(cur<<1));
			else W(ans,cur);
		}
	}
	for(int ck(0);ck*2<=n;++ck)
	{
		static int f[N][N][3];
		std::memset(f,0,sizeof(f));
		f[0][0][0]=1;
		for(int i(1);i<=n;++i)
		{
			for(int j(0);j<i;++j)
			{
				int c(2*j-(i-1));
				if(s[i]!=')')
				{
					if(c+1>ck) W(f[i][j+1][1],f[i-1][j][0]);
					else W(f[i][j+1][0],f[i-1][j][0]);
					W(f[i][j+1][1],f[i-1][j][1]);
					if(c+1<=(ck*2)) W(f[i][j+1][2],f[i-1][j][2]);
				}
				if(s[i]!='(')
				{
					if(c>0) W(f[i][j][0],f[i-1][j][0]),W(f[i][j][1],f[i-1][j][1]);
					else W(f[i][j][2],f[i-1][j][1]);
					W(f[i][j][2],f[i-1][j][2]);
				}
			}
		}
		int cur(0);
		for(int i(2);i<=n;i+=2) if(s[i]!=')')
		{
			for(int j(0);j<i;++j) if(2*j-(i-1)+1<=0)
			{
				int k((i-2-2*j)/2);
				if(2*j-(i-1)+1<0) cur=(cur+2ll*f[i-1][j][2]*g[i+1][(n-i)/2][ck+k])%p;
				else cur=(cur+1ll*f[i-1][j][2]*g[i+1][(n-i)/2][ck+k])%p;
			}
		}
		W(ans,cur);
	}
	return ans;
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin>>n>>(s+1);
	if(n&1){std::cout<<0<<std::endl;return 0;}
	int ans(solve());
	std::reverse(s+1,s+n+1);
	for(int i(1);i<=n;++i)
	{
		if(s[i]==')') s[i]='(';
		else if(s[i]=='(') s[i]=')';
	}
	W(ans,solve());std::cout<<1ll*ans*((p+1)/2)%p<<std::endl;
	return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4

Accepted

Test #1:

score: 4

Accepted

time: 112ms

memory: 470120kb

input:

2
xx

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 113ms

memory: 469896kb

input:

100
(()())()()()(()()(())(()))(())()(()()())(()())()()()(())((()()(()())(((()(()()()())((((()())))))))))

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 2ms

memory: 3456kb

input:

97
)((()(()(()))()(()(()))(((()(())()()())(())(((((()())))())())(()((()(())))(()())(()()())(()((())(

output:

result:

ok single line: '0'

Test #4:

score: 0

Accepted

time: 108ms

memory: 470008kb

input:

4
xxx(

output:

result:

ok single line: '6'

Test #5:

score: 0

Accepted

time: 119ms

memory: 470168kb

input:

34
)())()()(()(())(()(((()))))(()()((

output:

result:

ok single line: '0'

Test #6:

score: 0

Accepted

time: 125ms

memory: 470016kb

input:

44
))))x)((()(x())x)())x)(()()())))())())(((())

output:

result:

ok single line: '0'

Test #7:

score: 0

Accepted

time: 88ms

memory: 469956kb

input:

24
))(((xx)((((())xx((()()(

output:

result:

ok single line: '0'

Test #8:

score: 0

Accepted

time: 163ms

memory: 469932kb

input:

100
(()))(()))((((())))(()))))(()(x()((((((())))((())())))((()))((())(()((()(()((((()()(x)x)()))((((()((

output:

result:

ok single line: '0'

Test #9:

score: 0

Accepted

time: 156ms

memory: 469956kb

input:

100
)))))((()x))))())((())))(()))((()()()))())()))()))()(x((())(((())(()(()()((((()))))())(((((()))())()

output:

result:

ok single line: '3'

Test #10:

score: 0

Accepted

time: 126ms

memory: 469864kb

input:

100
))(()((x(()())x((()()(()))()))()))((()((())x)(((()()))()))(()))))(()(((((((()))())x()((((())(((()(()

output:

result:

ok single line: '0'

Test #11:

score: 0

Accepted

time: 131ms

memory: 469952kb

input:

24
(((x)(x)((()((x))()())))

output:

result:

ok single line: '8'

Test #12:

score: 0

Accepted

time: 115ms

memory: 470080kb

input:

78
()((()(((((((((((()()()())((()))((())((())())()()))((())(())))(()))()))))))))x

output:

result:

ok single line: '2'

Test #13:

score: 0

Accepted

time: 129ms

memory: 469984kb

input:

70
((((((()()))((())()(()((x))(((())(())()((())()((())))))(x)))(()x)))))x

output:

result:

ok single line: '14'

Test #14:

score: 0

Accepted

time: 132ms

memory: 470012kb

input:

52
(((()()()()x)(()))((((x)()(((((((())(((())xx))))))))

output:

result:

ok single line: '16'

Test #15:

score: 0

Accepted

time: 136ms

memory: 470076kb

input:

100
(())()()(()())(((((((((((((()((((())())((()(()()((())())))(()()))()(())(((((())())))))))))))))))))))

output:

result:

ok single line: '1'

Test #16:

score: 0

Accepted

time: 120ms

memory: 470072kb

input:

100
(()(())(())((((()(((((())(()((((()()()()()(())))x))()())()))((((())()((()())())((()()(()))))))))))))

output:

result:

ok single line: '2'

Test #17:

score: 0

Accepted

time: 142ms

memory: 469896kb

input:

100
()()xx()()()(()())()()()(())((x())((()()(())())((())())(()(()(())(())()(()())(x(()))))()()(((()())))

output:

result:

ok single line: '13'

Subtask #2:

score: 8

Accepted

Dependency #1:

100%

Accepted

Test #18:

score: 8

Accepted

time: 111ms

memory: 469896kb

input:

48
))()())())))(()((xx(())(x((((x(())(())((x((x))()

output:

result:

ok single line: '7'

Test #19:

score: 0

Accepted

time: 127ms

memory: 469896kb

input:

96
x)))))(()))))((())()())x)))((x((())())))())))))(()())(()())(())((x)x)))()(x(()((()(()))x(x())(()

output:

result:

ok single line: '0'

Test #20:

score: 0

Accepted

time: 140ms

memory: 470124kb

input:

28
)x)xxxx))()(())(((x()xx)xxxx

output:

result:

ok single line: '1621'

Test #21:

score: 0

Accepted

time: 151ms

memory: 470064kb

input:

86
(()xx())())(xx)(x(x))((((x())((xx(x((()))x(())(x)(()(((())())(()(()(((()((())))((())((

output:

result:

ok single line: '0'

Test #22:

score: 0

Accepted

time: 148ms

memory: 470068kb

input:

100
(((((())(()(x))())(((()(()()((()))))x()(())(())(x))(x))x)x)((((())x)x))))()((x(()((()(((x()()(((x()x

output:

result:

ok single line: '4096'

Test #23:

score: 0

Accepted

time: 130ms

memory: 470120kb

input:

100
)(())()x(()x))))))x)(()(x(((()((()()))))(())()()(()())x(x(((()(((()((()(((x))((()))))(()((((x)))x)()

output:

result:

ok single line: '0'

Test #24:

score: 0

Accepted

time: 136ms

memory: 470060kb

input:

100
x)()(()()x()))(()(()))()))((x))(())()(x)x)))())))())((()())x))((()()()(()(x()))x(xx))(((x))(x()()(()

output:

result:

ok single line: '114'

Test #25:

score: 0

Accepted

time: 129ms

memory: 469860kb

input:

78
(())()((())x(x(x))((x)(()(()((x())()x))()))(())())))()x(((((())))))(()()))()()

output:

result:

ok single line: '128'

Test #26:

score: 0

Accepted

time: 126ms

memory: 470160kb

input:

46
()(()x((xx()x(()(()(()(())())x(()x(x((x)x)))x)

output:

result:

ok single line: '1023'

Test #27:

score: 0

Accepted

time: 129ms

memory: 470080kb

input:

82
(())(x)())()()((((((()()((()((()()()xx(((x))))(())x)()))(x)x(x()()())()x(x()x))))x

output:

result:

ok single line: '2304'

Test #28:

score: 0

Accepted

time: 111ms

memory: 470124kb

input:

22
((xxx)xx((xx(xxx)))x)x

output:

result:

ok single line: '2720'

Test #29:

score: 0

Accepted

time: 140ms

memory: 469988kb

input:

100
(()((((())(x)(()()()()))()(())()))()((()()(()(((((x)xxx)x)(((x)))x()(()(x()(()()()))))()(((())))))))

output:

result:

ok single line: '512'

Test #30:

score: 0

Accepted

time: 151ms

memory: 469984kb

input:

100
((()()()())(()()(((()())(xx(())x))))))()()()()(()x()(()(((()))(()())))()(()())()()((())((xx())(())x)

output:

result:

ok single line: '128'

Test #31:

score: 0

Accepted

time: 132ms

memory: 470000kb

input:

100
()()((())((()(()()))))()()()()(()x()((xxx)())(x))()(()x)()()((())((x()(x)x)())((()x()())(())x)x(()))

output:

result:

ok single line: '4096'

Subtask #3:

score: 18

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #32:

score: 18

Accepted

time: 100ms

memory: 470176kb

input:

18
xx(xxxxxxxxxx)xxxx

output:

result:

ok single line: '33999'

Test #33:

score: 0

Accepted

time: 101ms

memory: 470008kb

input:

20
xxx()x(x(xxxxx)(xxxx

output:

result:

ok single line: '8324'

Test #34:

score: 0

Accepted

time: 117ms

memory: 470076kb

input:

34
xx)x((xxx(xxxx()x(xx)xx(xxxx()x)()

output:

result:

ok single line: '533461'

Test #35:

score: 0

Accepted

time: 124ms

memory: 470120kb

input:

16
xxxxxxxxxxxxxxxx

output:

result:

ok single line: '35708'

Test #36:

score: 0

Accepted

time: 129ms

memory: 470064kb

input:

100
))))()))x((()(x)(((xx(()x())(x(x)()x)()x)(()()x((x)()((((()))(x()()((())(x(())x))))((()())(()))((xx)

output:

result:

ok single line: '5861'

Test #37:

score: 0

Accepted

time: 144ms

memory: 469860kb

input:

100
(())())))(()(()((xx)(x()))(((((())(())(()(()((x())))()xx()))(x(x((()))()(x)))x)())((xx)(xxx()xx)()x)

output:

result:

ok single line: '141184'

Test #38:

score: 0

Accepted

time: 140ms

memory: 470064kb

input:

100
(()()x(((()(())))x(xx))((()(xx)()x(())x)(x)x()(xx)()))(())x)x()()x()x)(()()xx)(())(()(())(()xx)(())(

output:

result:

ok single line: '65704'

Test #39:

score: 0

Accepted

time: 111ms

memory: 469940kb

input:

16
xxxxxxxxxxxxxxxx

output:

result:

ok single line: '35708'

Test #40:

score: 0

Accepted

time: 113ms

memory: 469936kb

input:

86
(()()x)())(x)()()(xx)x(())x((x)x(x(()(x)(x()())(xx)(()((((xxx)x())x()()))))x))))(x()))

output:

result:

ok single line: '1014061'

Test #41:

score: 0

Accepted

time: 135ms

memory: 469936kb

input:

82
(((((()(())xx))(((x)((())x(x())x)(()(((x()x)(((xx)()()xx)xx(x))xx()x(())()))))x))x

output:

result:

ok single line: '690240'

Test #42:

score: 0

Accepted

time: 132ms

memory: 469952kb

input:

96
(()()xx)x)x)(()()((xx(xx()))))x())(()((x(()x))())(x()))(())x()(((x)((x(()())())(x()(())()(xxx))x

output:

result:

ok single line: '462358'

Test #43:

score: 0

Accepted

time: 114ms

memory: 470064kb

input:

100
((()(x))x((((((()())()x))x(x(x(())))()x)x(())()((()x()x(())x))))()))x(x))())((((x()((xxx(((x))))))x)

output:

result:

ok single line: '483680'

Test #44:

score: 0

Accepted

time: 119ms

memory: 469980kb

input:

100
()x(()))((()))()(((((x)()()xx()))(((x((x)((x()))x((((()((x(()((x)x()((()((x((x()))()x)())())x))))x))

output:

result:

ok single line: '33090'

Test #45:

score: 0

Accepted

time: 153ms

memory: 469896kb

input:

100
(((()((()x))()))(x((x)x((()(x((x))))x)x))))x()((()))(((((()())(xx)((x)))()()((()(x)(x(x))x)x()))xx)x

output:

result:

ok single line: '593205'

Subtask #4:

score: 43

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Test #46:

score: 43

Accepted

time: 135ms

memory: 469860kb

input:

2
xx

output:

result:

ok single line: '4'

Test #47:

score: 0

Accepted

time: 116ms

memory: 470076kb

input:

100
()((())()())(())()(()(()((()(()(()((()))())((()()))((()()()))))()(()(()((()((())))((())()(()))))))))

output:

result:

ok single line: '1'

Test #48:

score: 0

Accepted

time: 1ms

memory: 3448kb

input:

45
xxxxxxxxxx((x(x(xx((xxxxxxx(xx(xx(xxx)x(xxxxx

output:

result:

ok single line: '0'

Test #49:

score: 0

Accepted

time: 129ms

memory: 469896kb

input:

96
)xx)(()(xx(x)())x)x)x((xx)xxx()((x)x)x)x((x))x(((()))xxx(()xx(xxx)((()()(x(x()())xx)x)(xx(x()x()

output:

77848412

result:

ok single line: '77848412'

Test #50:

score: 0

Accepted

time: 119ms

memory: 470120kb

input:

60
xxxxxxx)xx(xxxxxx)xxxxx(xxxx(xx)x)xxxx)xxxxx(x(x(xx()xxx(xxx

output:

988515207

result:

ok single line: '988515207'

Test #51:

score: 0

Accepted

time: 130ms

memory: 470084kb

input:

22
xxxxxxxxxxxxxxxxxxxxxx

output:

result:

ok single line: '1955570'

Test #52:

score: 0

Accepted

time: 119ms

memory: 470020kb

input:

82
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

output:

598801371

result:

ok single line: '598801371'

Test #53:

score: 0

Accepted

time: 127ms

memory: 470120kb

input:

100
xxxx(x)x(x)x(xx))(x)xxxx(xxxx)(x(x(xx)x)(x()(x))(())xxxx)())(xxx((x()((xx()x((((xxxxxxx)xxxx)(x(xx))

output:

407359237

result:

ok single line: '407359237'

Test #54:

score: 0

Accepted

time: 141ms

memory: 469952kb

input:

100
xxxxxxxxx)x(xxxxx)xxxxxxx)x)xxx)x())xxxx(x(((xxxxxx(x((()xx)xx()xxxx))xxxxxxxx(xx(xx()x(x()xxxxx(x)x

output:

305743173

result:

ok single line: '305743173'

Test #55:

score: 0

Accepted

time: 126ms

memory: 470116kb

input:

100
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

output:

685691690

result:

ok single line: '685691690'

Test #56:

score: 0

Accepted

time: 120ms

memory: 470012kb

input:

44
(x)x)x(xxx)(())(()(()xxxx(xxxxxxx()()xxx((x)

output:

result:

ok single line: '1141552'

Test #57:

score: 0

Accepted

time: 131ms

memory: 469956kb

input:

36
xxxxx(xxxx(x)x(xxxxx(xxxxx)xxxx)xxxx

output:

200422525

result:

ok single line: '200422525'

Test #58:

score: 0

Accepted

time: 138ms

memory: 470008kb

input:

36
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

output:

543075284

result:

ok single line: '543075284'

Test #59:

score: 0

Accepted

time: 139ms

memory: 469900kb

input:

70
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

output:

286582712

result:

ok single line: '286582712'

Test #60:

score: 0

Accepted

time: 121ms

memory: 470012kb

input:

100
((xxxxxx)(xx(x(x(x((xx)xx((xxxx)xxxxx)x((xx)))((x)()x(xx)x((()()(xxxxx)(x)(x)xxx()(()xx)x))xx))xxxxx

output:

711075853

result:

ok single line: '711075853'

Test #61:

score: 0

Accepted

time: 137ms

memory: 469984kb

input:

100
()()((x)x())xxxxxx((xx()(xx)))xx)(()x()x(x)xx())((()(((x)x)x(x()(x))xx((xx(x()()()())))xx))x))x))))x

output:

819964975

result:

ok single line: '819964975'

Subtask #5:

score: 27

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Test #62:

score: 27

Accepted

time: 222ms

memory: 470168kb

input:

226
xxxxxxxxxxxxxxxxxxxx)xxxxxxxxxxxxxxxxxxxxxxxxxx(xxxxxxxxxx)xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx)xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx)xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx(xxxxxxxxxxxxxxxxxxxxxxx

output:

311662824

result:

ok single line: '311662824'

Test #63:

score: 0

Accepted

time: 171ms

memory: 470164kb

input:

222
x)())((xxx()x))x(x))x(xx(((xx)(x(((xxxx(x))x(x(xxx((xxx()xxxxxxxx))x(()()xxxxxxxx()x(xx)xxxxxx)(x(x(xxx(x))()((xx)(xxxx(xxxxx)xx(x())xx(x((xx)x)()xxx()xxxxx((x(((xxxxxxx(())x)xxxxxxx(xx()())xxxxx(xxxx())x())xxx(x())xx)x((x

output:

617635509

result:

ok single line: '617635509'

Test #64:

score: 0

Accepted

time: 148ms

memory: 469864kb

input:

158
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

output:

716446269

result:

ok single line: '716446269'

Test #65:

score: 0

Accepted

time: 145ms

memory: 469900kb

input:

134
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

output:

963748902

result:

ok single line: '963748902'

Test #66:

score: 0

Accepted

time: 276ms

memory: 470120kb

input:

300
xxxxxxxx)xx))xxxxx)xx(xx(xxx)xxxxx))xx))xx(xxxxx)xxx(xxxxxxxxxxx)xxxxxxxxxxx)xxxxxxx(xx(x)xxxx)xxxx)x)x)(x)x(x)))(xx(x(xx)xxxxxx)(xxxx(xxxxxx)xxxxxx)xxxxxxx(xxx)(x(xxx((x()xxxxxxxxxxx)xxxxxxxxx)xx(x(xxxxxxxx)xxxxxxxxxxxx)xxxx(xx()xxxxx)x(xxxxxxxxxx)xxxx(xxxxx()xxx)xxx)xxxxxxxxxxxx)xxxx)xxxxxxxxx...

output:

380753516

result:

ok single line: '380753516'

Test #67:

score: 0

Accepted

time: 250ms

memory: 470164kb

input:

300
)x)))x)x)x))xx)()()(x(xxx)x)(()x())(x()x((x)(())()x)xx)(xxxx))x)(x)x)x(((()(()))((()(x)()((xxx)(x)xxx)(x(())(()))())(())x()x)xx())x)(x)(xxx(x))((x)(((x)((()x()x))()x)))x)x))()()x((x)(((x(x))(((x)xx)))))(x)xx)x(x(((xxx)x(((xxx))x)xx()))x((xx()x)((x)(x(()xx)xx)))())))x((x(xx)x)x)((x)()()(xx()(x((x...

output:

674716216

result:

ok single line: '674716216'

Test #68:

score: 0

Accepted

time: 331ms

memory: 470064kb

input:

300
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

511488504

result:

ok single line: '511488504'

Test #69:

score: 0

Accepted

time: 128ms

memory: 469860kb

input:

166
((((()()))(())()()()(x))()x())(x((()x)(()x)((())())(x)()(xxx(())x(()()))((())(((x)x()((x)(x())((x()x)))(()xx)x)()()(xx((x())))())())xx()()()(())(())()((((x)()x(x)))x)

output:

254137024

result:

ok single line: '254137024'

Test #70:

score: 0

Accepted

time: 173ms

memory: 469864kb

input:

190
(x()()(((((())((()x()(x))((())(((())((()()(((()x())))((((((x))xx()x))())x()()))x()))()(x(x)((x)))(((())x)((((x())xx)x))x)x(x(x)())())((x((())x((()()))()(()))x)((((()))))(())(x))()))))x))))x)

output:

268435456

result:

ok single line: '268435456'

Test #71:

score: 0

Accepted

time: 139ms

memory: 470160kb

input:

116
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

output:

369003267

result:

ok single line: '369003267'

Test #72:

score: 0

Accepted

time: 160ms

memory: 470120kb

input:

136
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

output:

339830910

result:

ok single line: '339830910'

Test #73:

score: 0

Accepted

time: 313ms

memory: 470076kb

input:

300
(xx)xxx(x)(xxx)x)xxxxxxxxx(xxxx)((x(xx)xxxx((x(xxxx)xxxxxxxxx)xxx))xxxx)xxxxxxxx()xxxxxxxxxxxxxxxxxxxxx)xxxxxxxxxxxxxxx)xxxxxxx(xxxxxxxxx)xxxxxx)xxx((((xx)xxxx)xxxxxx(xxxxx)x()xx((xxxxxxxx)xxx)xxxxxxx(xxxxxxxxx)xx(xxxxxxxx)x)xxxxxx(xxxxxxxxxxxxxxx(xxxx)xx)xx)xxxx)xxxxxxxxxxxxxx)xxxxx)xxx)xxx)x)x...

output:

199242412

result:

ok single line: '199242412'

Test #74:

score: 0

Accepted

time: 224ms

memory: 470120kb

input:

300
(x(((()()()())(())((xx)))x((((()())()((x)((((((()))(()())())()())()))(((()((x((()x))((()())())(())()(xx))))()(((()()(()())()(x)x))x)())x(())())(x(()x())()())()))()))(())(((()(()()()(x()x)))(()(())))))))(x()()x)()()(((((()(()))(x)((()()()()))()(())))())()()()()((()))(())()(x(())x((())))()((())()(...

output:

result:

ok single line: '3858728'

Extra Test:

score: 0

Extra Test Passed