Submission #47769

#	Time	Username	Problem	Language	Result	Execution time	Memory
47769		Talant	Security Gate (JOI18_security_gate)	C++17	4 / 100	5020 ms	19524 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)

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:95:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
securitygate.cpp: In function 'int main()':
securitygate.cpp:101:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < a.size(); i ++) {
                       ~~^~~~~~~~~~
securitygate.cpp:114: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:96: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