Submission #69462

#	Time	Username	Problem	Language	Result	Execution time	Memory
69462		mohazar	Security Gate (JOI18_security_gate)	C++14	0 / 100	2 ms	488 KiB

securitygate

#include<bits/stdc++.h>
#define mp make_pair
#define fs first
#define sc second
#define pb push_back
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mod 998244353
using namespace std;

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

int n;
string s;
int a[305];
vector<int> ini;

bool check(){
	int pref = 0;
	for(int i = 0; i < n; i++){
		pref = pref + a[i];
		if(pref < 0) return false;
	}
	if(pref == 0) return true;
	return false;
}

int main(){
	cin >> n;
	cin >> s;
	if(n % 2 == 1){
		cout << "0\n";
		return 0;
	}
	int nyak = 0;
	for(int i = 0; i < n; i++){
		if(s[i] == 'x'){
			ini.pb(i);
			nyak++;
		}else if(s[i] == '('){
			a[i] = 1;
		}else{
			a[i] = -1;
		}
	}	

	int maks = (1 << nyak);
	int cnt = 0;

	for(int i = 0; i < maks; i++){
		for(int j = 0; j < ini.size(); j++){
			int pos = ini[j];
			if((i & (1 << j)) > 0){
				a[pos] = 1;
			}else{
				a[pos] = -1;
			}
		}
		bool bisa = false;
		for(int p = 0; p < n; p++){
			for(int q = p; q < n; q++){
				for(int r = p; r <= q; r++) a[r] = -a[r];
				if(check()) bisa = true;
				for(int r = p; r <= q; r++) a[r] = -a[r];
				if(bisa) break;
			}
			if(bisa) break;
		}
		if(bisa){
			cnt++;
		}
	}
	cout << cnt << "\n";
}

Compilation message (stderr)

securitygate.cpp: In function 'int main()':
securitygate.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < ini.size(); j++){
                  ~~^~~~~~~~~~~~

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