Submission #1222539

#TimeUsernameProblemLanguageResultExecution timeMemory
1222539PenguinsAreCuteSecurity Gate (JOI18_security_gate)C++17
12 / 100
5067 ms412 KiB
#include <bits/stdc++.h>
using namespace std;
bool bracket(string s) {
	int ps = 0;
	for(auto i: s) {
		ps += (i == '(' ? 1 : -1);
		if(ps < 0)
			return 0;
	}
	return !ps;
}
bool yey(string s) {
	if(bracket(s))
		return 1;
	int n = s.size();
	for(int l=0;l<n;l++)
		for(int r=l+1;r<=n;r++) {
			string t = s;
			for(int i=l;i<r;i++)
				t[i] ^= '(' ^ ')';
			if(bracket(t))
				return 1;
		}
	return 0;
}
int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cnt = 0;
	vector<int> px;
	for(int i=0;i<n;i++)
		if(s[i] == 'x')
			px.push_back(i);
	int m = px.size();
	for(int i=0;i<(1<<m);i++) {
		string t = s;
		for(int j=0;j<m;j++)
			t[px[j]] = (i & (1 << j) ? '(' : ')');
		if(yey(t))
			cnt++;
	}
	cout << cnt;
}
#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...