Submission #57721

#TimeUsernameProblemLanguageResultExecution timeMemory
57721ksun48Security Gate (JOI18_security_gate)C++14
12 / 100
5090 ms740 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD = 1000000007; const int MAXN = 110; 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--; } vector<int> endlists[2 * MAXN]; vector<int> psumlists[2 * MAXN]; int ecuridx[2 * MAXN]; int pcuridx[2 * MAXN]; for(int j = laste; j <= psums.size() - 1; j++){ endlists[MAXN + psums[j]].push_back(j); ecuridx[MAXN + psums[j]] = 0; } for(int j = 0; j <= psums.size() - 1; j++){ psumlists[MAXN + psums[j]].push_back(j); pcuridx[MAXN + psums[j]] = 0; } int a = psums[psums.size() - 1] / 2; for(int j = 0; j < psums.size(); j++){ if(psums[j] < 0) break; int need = psums[j] + a; vector<int>& z = endlists[MAXN + need]; int idx = ecuridx[MAXN + need]; if(idx < z.size()){ int e = z[idx]; // check if all elements in [j,e] are <= vector<int>& w = psumlists[MAXN + 2 * psums[j] + 1]; int idx2 = pcuridx[MAXN + 2 * psums[j] + 1]; if(idx2 < w.size() && w[idx2] <= e){ } else { return 1; } } if(j >= laste){ ecuridx[MAXN + psums[j]]++; } pcuridx[MAXN + psums[j]]++; } return 0; } LL cnt(string s, int idx){ if(idx == s.size()) 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:9:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < s.size(); j++){
                 ~~^~~~~~~~~~
securitygate.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = laste; j <= psums.size() - 1; j++){
                     ~~^~~~~~~~~~~~~~~~~~~
securitygate.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j <= psums.size() - 1; j++){
                 ~~^~~~~~~~~~~~~~~~~~~
securitygate.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < psums.size(); j++){
                 ~~^~~~~~~~~~~~~~
securitygate.cpp:38:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(idx < z.size()){
      ~~~~^~~~~~~~~~
securitygate.cpp:43:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(idx2 < w.size() && w[idx2] <= e){
       ~~~~~^~~~~~~~~~
securitygate.cpp: In function 'LL cnt(std::__cxx11::string, int)':
securitygate.cpp:57:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(idx == s.size()) return check(s);
     ~~~~^~~~~~~~~~~
securitygate.cpp:65:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int z = idx + 1; z <= s.size(); z++){
                       ~~^~~~~~~~~~~
securitygate.cpp:66:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(z == s.size() || s[z] == 'x'){
      ~~^~~~~~~~~~~
securitygate.cpp:70: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...