Submission #58182

#TimeUsernameProblemLanguageResultExecution timeMemory
58182ksun48Security Gate (JOI18_security_gate)C++14
12 / 100
5047 ms880 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD = 1000000007; LL check(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 minv = 0; int maxv = 0; int a = psums[psums.size()-1] / 2; for(int i = 0; i < psums.size(); i++){ if(i <= lasts){ minv = min(minv, max(0,psums[i])); maxv = max(maxv, psums[i]); } while(minv <= maxv && minv * 2 < psums[i]) minv++; if(i >= laste){ int b = psums[i]-a; if(b >= minv && b <= maxv) return 1; } } return 0; } 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 cnt(string s, int idx){ if(idx == s.size()){ if(check(s) != check2(s)){ cout << s << " " << check(s) << " " << check2(s) << endl; assert(0); } return check(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 << cnt(s, 0) << '\n'; }

Compilation message (stderr)

securitygate.cpp: In function 'LL check(std::__cxx11::string)':
securitygate.cpp:8:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < s.size(); j++){
                 ~~^~~~~~~~~~
securitygate.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(lasts + 1 < psums.size() && psums[lasts + 1] >= psums[0]){
        ~~~~~~~~~~^~~~~~~~~~~~~~
securitygate.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < psums.size(); i++){
                 ~~^~~~~~~~~~~~~~
securitygate.cpp: In function 'LL check2(std::__cxx11::string)':
securitygate.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < s.size(); j++){
                 ~~^~~~~~~~~~
securitygate.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(lasts + 1 < psums.size() && psums[lasts + 1] >= psums[0]){
        ~~~~~~~~~~^~~~~~~~~~~~~~
securitygate.cpp:58:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(lasts == psums.size() - 1 && laste == 0){
     ~~~~~~^~~~~~~~~~~~~~~~~~~
securitygate.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  } else if(lasts == psums.size() - 1){
            ~~~~~~^~~~~~~~~~~~~~~~~~~
securitygate.cpp:62:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = laste; i < psums.size(); i++){
                      ~~^~~~~~~~~~~~~~
securitygate.cpp:74:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = lasts; i < psums.size(); i++){
                      ~~^~~~~~~~~~~~~~
securitygate.cpp:88:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = laste; i < psums.size(); i++){
                      ~~^~~~~~~~~~~~~~
securitygate.cpp: In function 'LL cnt(std::__cxx11::string, int)':
securitygate.cpp:97:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(idx == s.size()){
     ~~~~^~~~~~~~~~~
securitygate.cpp:111:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int z = idx + 1; z <= s.size(); z++){
                       ~~^~~~~~~~~~~
securitygate.cpp:112:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(z == s.size() || s[z] == 'x'){
      ~~^~~~~~~~~~~
securitygate.cpp:116: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...