Submission #1221605

#TimeUsernameProblemLanguageResultExecution timeMemory
1221605emptypringlescanSecurity Gate (JOI18_security_gate)C++17
0 / 100
0 ms328 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...