제출 #47786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47786		Talant	Security Gate (JOI18_security_gate)	C++17	4 / 100	5039 ms	38348 KiB

securitygate

#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 || b[0] == ')')
                        break;
            }
      }
      cout << ans % inf << endl;
}

컴파일 시 표준 에러 (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);
       ^~~~

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