Submission #47767

#TimeUsernameProblemLanguageResultExecution timeMemory
47767TalantSecurity Gate (JOI18_security_gate)C++17
0 / 100
16 ms19068 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) 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 ++; f = 1; break; } } if (f) break; } } cout << ans << 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);
       ^~~~
#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...