#include <bits/stdc++.h>
using namespace std;
int n;
string s;
const long long mod=1000000007;
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
if(n&1){
cout << 0;
return 0;
}
vector<int> pos;
for(int i=0; i<n; i++){
if(s[i]=='x') pos.push_back(i);
}
int ans=0;
for(int bm=0; bm<(1<<(int)pos.size()); bm++){
int arr[n+5];
memset(arr,0,sizeof(arr));
for(int i=0; i<(int)pos.size(); i++){
if(bm&(1<<i)) arr[pos[i]]=1;
else arr[pos[i]]=-1;
}
for(int i=0; i<n; i++){
if(s[i]=='(') arr[i]=1;
else if(s[i]==')') arr[i]=-1;
}
for(int i=1; i<n; i++) arr[i]+=arr[i-1];
bool can=false;
pair<int,int> mx={0,0},mx2={-1e9,n-1},hm;
for(int i=0; i<n; i++){
if(arr[i]<0){
hm.first=i;
break;
}
else mx=max(mx,{arr[i],i+1});
if(i==n-1){
ans++;
can=true;
}
}
if(can) continue;
for(int i=n-1; i>=0; i--){
if(arr[i]-arr[n-1]<0){
hm.second=i;
break;
}
else mx2=max(mx2,{arr[i],i-1});
if(i==0&&arr[n-1]<=0){
ans++;
can=true;
}
}
if(can) continue;
int mx3=0;
for(int i=hm.first; i<=hm.second; i++) mx3=max(mx3,arr[i]);
int x=arr[n-1];
if(mx.first>=x/2&&mx3<=min(2*mx.first,2*mx2.first-x)){
ans++;
}
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |