#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; 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
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);
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
