Submission #58407

#TimeUsernameProblemLanguageResultExecution timeMemory
58407ksun48Security Gate (JOI18_security_gate)C++14
0 / 100
5005 ms848 KiB
#include <bits/stdc++.h> using namespace std; typedef int 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++){ auto& rp = dp[i + 1][OFF + j + 1]; auto& rz = dp[i][OFF + j]; auto& rm = dp[i + 1][OFF + j - 1]; 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++){ 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 = 0; r < MAXS; r++){ 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++){ auto& rp = dp[i + 1][OFF + j + 1]; auto& rz = dp[i][OFF + j]; auto& rm = dp[i + 1][OFF + j - 1]; 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++){ 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) + case2(t) + case3(s); } 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:152:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int m = 0; m <= s.size(); m++){
                  ~~^~~~~~~~~~~
securitygate.cpp:157:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i <= s.size(); i++){
                   ~~^~~~~~~~~~~
securitygate.cpp:167: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:218: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:227:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(idx == s.size()){
     ~~~~^~~~~~~~~~~
securitygate.cpp:237:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int z = idx + 1; z <= s.size(); z++){
                       ~~^~~~~~~~~~~
securitygate.cpp:238:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(z == s.size() || s[z] == 'x'){
      ~~^~~~~~~~~~~
securitygate.cpp:242:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#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...