Submission #47770

#TimeUsernameProblemLanguageResultExecution timeMemory
47770TalantSecurity Gate (JOI18_security_gate)C++17
4 / 100
5027 ms38304 KiB
#include <bits/stdc++.h> #define mk make_pair #define sc second #define fr first #define pb emplace_back #define all(s) s.begin(), s.end() #define sz(s) ( (int)s.size() ) #define Scan(a) scanf ("%I64d", &a) #define scan(a) scanf ("%d", &a) #define int long long using namespace std; const int inf = (int)1e9 + 7; const int N = (int)2e5 + 7; int n; int c; int ans; string a,b; struct node { int op,cl,cn; int _op,_cl,_cn; node() { op = cl = cn = 0; _op = _cl = _cn = 0; } }t[N * 4]; node merge (node a,node b) { node c; c.cn = (a.cn + b.cn); int o = min(a.op,b.cl); c.cn += o; a.op -= o; b.cl -= o; c.op = a.op + b.op; c.cl = a.cl + b.cl; c._cn = (a._cn + b._cn); o = min(a._cl,b._op); c._cn += o; a._cl -= o; b._op -= o; c._op = a._op + b._op; c._cl = a._cl + b._cl; return c; } void build (int v = 1,int tl = 0,int tr = n - 1) { if (tl == tr) { if (b[tl] == '(') t[v].op = t[v]._op = 1; else t[v].cl = t[v]._cl = 1; } else { int tm = (tl + tr) >> 1; build (v + v,tl,tm); build (v + v + 1,tm + 1,tr); t[v] = merge(t[v + v],t[v + v + 1]); } } void update (int pos,int x,int v = 1,int tl = 0,int tr = n - 1) { if (tl == tr) { if (x == 1){ t[v].op = 1,t[v].cl = 0; t[v]._op = 1,t[v]._cl = 0; } else { t[v].cl = 1,t[v].op = 0; t[v]._cl = 1,t[v]._op = 0; } } else { int tm = (tl + tr) >> 1; if (pos <= tm) update (pos,x,v + v,tl,tm); else update (pos,x,v + v + 1,tm + 1,tr); t[v] = merge(t[v + v],t[v + v + 1]); } } node get (int l,int r,int v = 1,int tl = 0,int tr = n - 1) { node cur; if (l > r || tl > r || tr < l) return cur; if (l <= tl && tr <= r) return t[v]; int tm = (tl + tr) >> 1; return merge(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr)); } vector <int> v; main () { Scan(n); cin >> a; b = a; for (int i = 0; i < a.size(); i ++) { if (a[i] == 'x') { v.pb(i); c ++; b[i] = '('; } } if (c > 20 || (n & 1)) { cout << 0 << endl; return 0; } build(); for (int i = 0; i < (1 << c); i ++) { for (int j = 0; j < v.size(); j ++) { if (i & (1 << j)) update (v[j],1); else update (v[j],2); } int f = 0; for (int ii = 0; ii < n; ii ++) { for (int j = ii - 1; j < n; j ++) { node aa = get(0,ii - 1); node bb = get(ii,j); node cc = get(j + 1,n - 1); node cur; cur.cn = bb._cn;cur.op = bb._cl;cur.cl = bb._op; aa = merge(aa,cur); aa = merge(aa,cc); if (aa.cn == n / 2) { ans ++; ans %= inf; f = 1; break; } } if (f) break; } } cout << ans % inf << endl; }

Compilation message (stderr)

securitygate.cpp:96:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
securitygate.cpp: In function 'int main()':
securitygate.cpp:9:35: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
 #define Scan(a) scanf ("%I64d", &a)
                                 ~~^~
 #define scan(a) scanf ("%d", &a)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  
 #define int long long
 ~~~~~~~~~~~~~~~~~~~~~~             
 
 ~                                  
 using namespace std;
 ~~~~~~~~~~~~~~~~~~~~~              
 
 ~                                  
 const int inf = (int)1e9 + 7;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~     
 const int N = (int)2e5 + 7;
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~       
 
 ~                                  
 int n;
 ~~~~~~~                            
 int c;
 ~~~~~~~                            
 int ans;
 ~~~~~~~~~                          
 
 ~                                  
 string a,b;
 ~~~~~~~~~~~~                       
 
 ~                                  
 struct node {
 ~~~~~~~~~~~~~~                     
       int op,cl,cn;
       ~~~~~~~~~~~~~~               
       int _op,_cl,_cn;
       ~~~~~~~~~~~~~~~~~            
       node() {
       ~~~~~~~~~                    
             op = cl = cn = 0;
             ~~~~~~~~~~~~~~~~~~     
             _op = _cl = _cn = 0;
             ~~~~~~~~~~~~~~~~~~~~~  
       }
       ~~                           
 }t[N * 4];
 ~~~~~~~~~~~                        
 
 ~                                  
 node merge (node a,node b) {
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~      
       node c;
       ~~~~~~~~                     
 
 ~                                  
       c.cn = (a.cn + b.cn);
       ~~~~~~~~~~~~~~~~~~~~~~       
       int o = min(a.op,b.cl);
       ~~~~~~~~~~~~~~~~~~~~~~~~     
       c.cn += o;
       ~~~~~~~~~~~                  
       a.op -= o;
       ~~~~~~~~~~~                  
       b.cl -= o;
       ~~~~~~~~~~~                  
       c.op = a.op + b.op;
       ~~~~~~~~~~~~~~~~~~~~         
       c.cl = a.cl + b.cl;
       ~~~~~~~~~~~~~~~~~~~~         
 
 ~                                  
       c._cn = (a._cn + b._cn);
       ~~~~~~~~~~~~~~~~~~~~~~~~~    
       o = min(a._cl,b._op);
       ~~~~~~~~~~~~~~~~~~~~~~       
       c._cn += o;
       ~~~~~~~~~~~~                 
       a._cl -= o;
       ~~~~~~~~~~~~                 
       b._op -= o;
       ~~~~~~~~~~~~                 
       c._op = a._op + b._op;
       ~~~~~~~~~~~~~~~~~~~~~~~      
       c._cl = a._cl + b._cl;
       ~~~~~~~~~~~~~~~~~~~~~~~      
       return c;
       ~~~~~~~~~~                   
 }
 ~~                                 
 void build (int v = 1,int tl = 0,int tr = n - 1) {
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
       if (tl == tr) {
       ~~~~~~~~~~~~~~~~             
             if (b[tl] == '(') t[v].op = t[v]._op = 1;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             else t[v].cl = t[v]._cl = 1;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
       }
       ~~                           
       else {
       ~~~~~~~                      
             int tm = (tl + tr) >> 1;
             ~~~~~~~~~~~~~~~~~~~~~~~~~
             build (v + v,tl,tm);
             ~~~~~~~~~~~~~~~~~~~~~  
             build (v + v + 1,tm + 1,tr);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             t[v] = merge(t[v + v],t[v + v + 1]);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
       }
       ~~                           
 }
 ~~                                 
 void update (int pos,int x,int v = 1,int tl = 0,int tr = n - 1) {
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
       if (tl == tr) {
       ~~~~~~~~~~~~~~~~             
             if (x == 1){
             ~~~~~~~~~~~~~          
                   t[v].op = 1,t[v].cl = 0;
                   ~~~~~~~~~~~~~~~~~~~~~~~~~
                   t[v]._op = 1,t[v]._cl = 0;
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~
             }
             ~~                     
             else {
             ~~~~~~~                
                   t[v].cl = 1,t[v].op = 0;
                   ~~~~~~~~~~~~~~~~~~~~~~~~~
                   t[v]._cl = 1,t[v]._op = 0;
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~
             }
             ~~                     
       }
       ~~                           
       else {
       ~~~~~~~                      
             int tm = (tl + tr) >> 1;
             ~~~~~~~~~~~~~~~~~~~~~~~~~
             if (pos <= tm)
             ~~~~~~~~~~~~~~~        
                   update (pos,x,v + v,tl,tm);
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             else
             ~~~~~                  
                   update (pos,x,v + v + 1,tm + 1,tr);
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             t[v] = merge(t[v + v],t[v + v + 1]);
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
       }
       ~~                           
 }
 ~~                                 
 node get (int l,int r,int v = 1,int tl = 0,int tr = n - 1) {
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
       node cur;
       ~~~~~~~~~~                   
       if (l > r || tl > r || tr < l)
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             return cur;
             ~~~~~~~~~~~~           
       if (l <= tl && tr <= r)
       ~~~~~~~~~~~~~~~~~~~~~~~~     
             return t[v];
             ~~~~~~~~~~~~~          
       int tm = (tl + tr) >> 1;
       ~~~~~~~~~~~~~~~~~~~~~~~~~    
       return merge(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr));
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 }
 ~~                                 
 vector <int> v;
 ~~~~~~~~~~~~~~~~                   
 
 ~                                  
 main () {
 ~~~~~~~~~~                         
       Scan(n);
       ~~~~~~                       
securitygate.cpp:97:7: note: in expansion of macro 'Scan'
       Scan(n);
       ^~~~
securitygate.cpp:102:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < a.size(); i ++) {
                       ~~^~~~~~~~~~
securitygate.cpp:116:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < v.size(); j ++) {
                             ~~^~~~~~~~~~
securitygate.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define Scan(a) scanf ("%I64d", &a)
                 ~~~~~~^~~~~~~~~~~~~
securitygate.cpp:97:7: note: in expansion of macro 'Scan'
       Scan(n);
       ^~~~
#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...