Submission #70827398

---

Source Code Expand

#include<bits/stdc++.h>
#define cmin(a,b) a=std::min(a,b)
#define cmax(a,b) a=std::max(a,b)
#define inf
#define mod
#define maxn 1000006
#define int long long
int T,n,K,to[maxn];
char s[maxn]; 
int que[maxn],bk;
signed main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%s%lld",s+1,&K);
		n=strlen(s+1);
		#define quit(x) puts(((x)==2)?"Second":"First");
		int cnt=0,flag=0;bk=0;
		for(int i=1;i<=n;i++){
			if(s[i]=='(') cnt++,que[++bk]=i;
			else cnt--,to[que[bk--]]=i;
			if(cnt<0) flag=1;
		}
		if(cnt!=0||flag||(n&1)||(K&1)){
			puts("First");continue; 
		}
		int L=1,R=n;cnt=(n-K)/2;
		while(cnt&&to[L]==R){
			cnt--,L++,R--; 
		}
		int cnt1=0,cnt2=0;
		for(int i=L;i<=R&&s[i]=='('&&s[i+1]==')';i+=2){
			cnt1++;
		}
		for(int i=R;i>=L&&s[i-1]=='('&&s[i]==')';i-=2){
			cnt2++;
		}
//		printf("%lld %lld\n",cnt1,cnt2);
		if(std::min(cnt1,cnt2)<cnt) flag=1;
		puts(flag?"First":"Second");
	}
	return 0;
}
/*
2
((()()((()())())()))
12
((()()((()())())()))
14
*/

Submission Info

Judge Result