Submission #58417

#	Time	Username	Problem	Language	Result	Execution time	Memory
58417		ksun48	Security Gate (JOI18_security_gate)	C++14	73 / 100	4652 ms	1876 KiB

securitygate

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL MOD = 1000000007;
const LL OFF = 101;
const LL MAXS = 204;
LL check2(string s){
	vector<int> psums(1,0);
	for(int j = 0; j < s.size(); j++){
		if(s[j] == '('){
			psums.push_back(psums[psums.size() - 1] + 1);
		} else {
			psums.push_back(psums[psums.size() - 1] - 1);
		}
	}
	int laste = psums.size() - 1;
	while(laste > 0 && psums[laste - 1] >= psums[psums.size() - 1]){
		laste--;
	}
	int lasts = 0;
	while(lasts + 1 < psums.size() && psums[lasts + 1] >= psums[0]){
		lasts++;
	}
	int a = psums[psums.size() - 1] / 2;
	if(lasts == psums.size() - 1 && laste == 0){
		return 1;
	} else if(lasts == psums.size() - 1){
		int maxv = 0;
		for(int i = laste; i < psums.size(); i++){
			maxv = max(maxv, psums[i] - psums[psums.size() - 1]);
		}
		for(int i = laste; i >= 0; i--){
			if(psums[i] - psums[psums.size() - 1] <= maxv - a) return 1;
			if(psums[i] - psums[psums.size() - 1] > 2 * maxv) return 0;
		}
	} else if(laste == 0){
		int maxv = 0;
		for(int i = 0; i <= lasts; i++){
			maxv = max(maxv, psums[i]);
		}
		for(int i = lasts; i < psums.size(); i++){
			if(psums[i] <= maxv + a) return 1;
			if(psums[i] > 2 * maxv) return 0;
		}
	} else {
		int maxl = psums[0];
		int maxm = psums[lasts];
		int maxr = psums[psums.size() - 1];
		for(int i = 0; i <= lasts; i++){
			maxl = max(maxl, psums[i]);
		}
		for(int i = lasts; i <= laste; i++){
			maxm = max(maxm, psums[i]);
		}
		for(int i = laste; i < psums.size(); i++){
			maxr = max(maxr, psums[i]);
		}	
		return (maxm <= 2 * maxl && maxm <= 2 * (maxr - a));
	}
	return 0;
}

LL case1(string s){
	// how many correct bracket sequences are there
	LL dp[s.size() + 1][MAXS];
	for(int i = 0; i <= s.size(); i++){
		for(int j = 0; j < MAXS; j++){
			dp[i][j] = 0;
		}
	}
	dp[0][OFF] = 1;
	for(int i = 0; i < s.size(); i++){
		for(int j = 0; j <= i; j++){
			if(s[i] != ')'){
				dp[i + 1][OFF + j + 1] += dp[i][OFF + j];
			}
			if(s[i] != '('){
				dp[i + 1][OFF + j - 1] += dp[i][OFF + j];
			}
		}
		for(int j = 0; j < MAXS; j++){
			dp[i + 1][j] %= MOD;
		}
	}
	return dp[s.size()][OFF];
}
LL case2(string s){
	// phases:
	// not found max, found max, gone negative, found a + b/2
	LL ans = 0;
	int z = s.size();
	for(int b = -z; b < 0; b += 2){
		for(int m = 0; m <= s.size(); m++){
			LL dp[s.size() + 1][MAXS][4]; // i, pos, 
			for(int i = 0; i <= s.size(); i++){
				for(int r = 0; r < MAXS; r++){
					for(int c = 0; c < 4; c++){
						dp[i][r][c] = 0;
					}
				}
			}
			dp[0][OFF][(m == 0)] = 1;
			for(int i = 0; i < s.size(); i++){
				for(int j = -z; j <= z; j++){
					if((i + j) % 2) continue;
					if(abs(j-b) > (s.size() - i)) continue;
					auto& rp = dp[i + 1][OFF + j + 1];
					auto& rz = dp[i][OFF + j];
					auto& rm = dp[i + 1][OFF + j - 1];
					if(!rz[0] && !rz[1] && !rz[2] && !rz[3]) continue;
					if(s[i] != ')'){
						if(j + 1 <= m){
							rp[(j + 1 == m)] += rz[0];
							rp[1] += rz[1];
						}
						if(j + 1 <= 2 * m){
							rp[2] += rz[2];
						}
						rp[3] += rz[3];
					}
					if(s[i] != '('){
						if(j - 1 >= b){
							if(j - 1 >= 0){
								rm[0] += rz[0];
								rm[1] += rz[1];
							} else {
								rm[2 + (j - 1 <= m + b/2)] += rz[1];
							}
							rm[2 + (j - 1 <= m + b/2)] += rz[2];
							rm[3] += rz[3];
						}
					}
				}
				for(int j = 0; j < MAXS; j++){
					for(int c = 0; c < 4; c++){
						if(dp[i + 1][j][c] >= MOD) dp[i + 1][j][c] %= MOD;
					}
				}
			}
			ans += dp[s.size()][OFF + b][3];
			ans %= MOD;
			if(dp[s.size()][OFF + b][3] > 0){
				//cout << m << " " << b << " " << dp[s.size()][OFF + b][3] << endl;
			}
		}
	}
	return ans;
}
LL case3(string s){
	// do shitty n^4 dp here
	LL ans = 0;
	int z = s.size();
	for(int b = -z; b <= z; b += 2){
		for(int m = 0; m <= s.size(); m++){
			if(m < b) continue;
			// phases: 
			// not hit needed, hit needed, went negative, hit max, went positive, hit needed
			LL dp[s.size() + 1][MAXS][6];
			for(int i = 0; i <= s.size(); i++){
				for(int r = (i + OFF) % 2; r < MAXS; r+= 2){
					for(int c = 0; c < 6; c++){
						dp[i][r][c] = 0;
					}
				}
			}
			int lneeded = (m + 1) / 2;
			int rneeded = lneeded + b/2;
			dp[0][OFF][(0 >= lneeded)] = 1;
			for(int i = 0; i < s.size(); i++){
				for(int j = -z; j <= z; j++){
					if((i + j) % 2) continue;
					if(abs(j-b) > (s.size() - i)) continue;
					auto& rp = dp[i + 1][OFF + j + 1];
					auto& rz = dp[i][OFF + j];
					auto& rm = dp[i + 1][OFF + j - 1];
					if(!rz[0] && !rz[1] && !rz[2] && !rz[3] && !rz[4] && !rz[5]) continue;
					if(s[i] != ')'){
						rp[(j + 1 >= lneeded)] += rz[0];
						rp[1] += rz[1];
						if(j + 1 <= m){
							rp[2 + (j + 1 == m)] += rz[2];
							rp[3] += rz[3];
							if(j + 1 == b){
								if(j + 1 == m){
									rp[4 + (j + 1 >= rneeded)] += rz[2];
								}
								rp[4 + (j + 1 >= rneeded)] += rz[3];
							}
						}
						rp[4 + (j + 1 >= rneeded)] += rz[4];
						rp[5] += rz[5];
					}
					if(s[i] != '('){
						if(j - 1 >= 0){
							rm[0] += rz[0];
							rm[1] += rz[1];
						} else {
							rm[2 + (m == 0)] += rz[1];
						}
						rm[2] += rz[2];
						rm[3] += rz[3];
						if(j - 1 >= b){
							rm[4] += rz[4];
							rm[5] += rz[5];
						}
					}
				}
				for(int j = 0; j < MAXS; j++){
					for(int c = 0; c < 6; c++){
						if(dp[i + 1][j][c] >= MOD) dp[i + 1][j][c] %= MOD;
					}
				}
			}
			ans += dp[s.size()][OFF + b][5];
			ans %= MOD;
		}
	}
	return ans;
}
LL solve(string s){
	string t = s;
	reverse(t.begin(), t.end());
	for(int i = 0; i < t.size(); i++){
		if(t[i] != 'x'){
			t[i] = '(' + ')' - t[i];
		}
	}
	return ((case1(s) + case2(s)) % MOD + (case2(t) + case3(s)) % MOD) % MOD;
}

LL cnt(string s, int idx){
	if(idx == s.size()){
		return check2(s);
	}
	if(s[idx] != 'x'){
		return cnt(s, idx + 1);
	}
	string s1 = s;
	string s2 = s;
	s1[idx] = '(';
	s2[idx] = ')';
	for(int z = idx + 1; z <= s.size(); z++){
		if(z == s.size() || s[z] == 'x'){
			return (cnt(s1, z) + cnt(s2, z)) % MOD;
		}
	}
}
int main(){
	int n;
	string s;
	cin >> n >> s;
	if(n % 2 == 1){
		cout << 0 << '\n';
		return 0;
	}
	cout << solve(s) << '\n';
}

Compilation message (stderr)

securitygate.cpp: In function 'LL check2(std::__cxx11::string)':
securitygate.cpp:10:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < s.size(); j++){
                 ~~^~~~~~~~~~
securitygate.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(lasts + 1 < psums.size() && psums[lasts + 1] >= psums[0]){
        ~~~~~~~~~~^~~~~~~~~~~~~~
securitygate.cpp:26:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(lasts == psums.size() - 1 && laste == 0){
     ~~~~~~^~~~~~~~~~~~~~~~~~~
securitygate.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  } else if(lasts == psums.size() - 1){
            ~~~~~~^~~~~~~~~~~~~~~~~~~
securitygate.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = laste; i < psums.size(); i++){
                      ~~^~~~~~~~~~~~~~
securitygate.cpp:42:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = lasts; i < psums.size(); i++){
                      ~~^~~~~~~~~~~~~~
securitygate.cpp:56:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = laste; i < psums.size(); i++){
                      ~~^~~~~~~~~~~~~~
securitygate.cpp: In function 'LL case1(std::__cxx11::string)':
securitygate.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i <= s.size(); i++){
                 ~~^~~~~~~~~~~
securitygate.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++){
                 ~~^~~~~~~~~~
securitygate.cpp: In function 'LL case2(std::__cxx11::string)':
securitygate.cpp:94:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int m = 0; m <= s.size(); m++){
                  ~~^~~~~~~~~~~
securitygate.cpp:96:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i <= s.size(); i++){
                   ~~^~~~~~~~~~~
securitygate.cpp:104:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < s.size(); i++){
                   ~~^~~~~~~~~~
securitygate.cpp: In function 'LL case3(std::__cxx11::string)':
securitygate.cpp:155:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int m = 0; m <= s.size(); m++){
                  ~~^~~~~~~~~~~
securitygate.cpp:160:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i <= s.size(); i++){
                   ~~^~~~~~~~~~~
securitygate.cpp:170:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < s.size(); i++){
                   ~~^~~~~~~~~~
securitygate.cpp: In function 'LL solve(std::__cxx11::string)':
securitygate.cpp:224:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++){
                 ~~^~~~~~~~~~
securitygate.cpp: In function 'LL cnt(std::__cxx11::string, int)':
securitygate.cpp:233:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(idx == s.size()){
     ~~~~^~~~~~~~~~~
securitygate.cpp:243:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int z = idx + 1; z <= s.size(); z++){
                       ~~^~~~~~~~~~~
securitygate.cpp:244:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(z == s.size() || s[z] == 'x'){
      ~~^~~~~~~~~~~
securitygate.cpp:248:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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