Submission #1221602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221602		emptypringlescan	Security Gate (JOI18_security_gate)	C++17	In queue	0 ms	0 KiB

securitygate

#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;
}