Submission #1222539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222539		PenguinsAreCute	Security Gate (JOI18_security_gate)	C++17	12 / 100	5067 ms	412 KiB

securitygate

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

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 43
• Subtask 5: 0 / 27