Submission #1091564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091564		hungcubuso1vn	Security Gate (JOI18_security_gate)	C++17	0 / 100	0 ms	348 KiB

securitygate

#include         <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma             GCC   optimize("Ofast")

#define            TASK   ""
#define              ll   long long
#define             ull   unsigned ll
#define              db   long double
#define             pLL   pair<ll, ll>
#define             pLI   pair<ll, int>
#define             pIL   pair<int, ll>
#define             pII   pair<int, int>
#define             vec   vector
#define              vL   vec<ll>
#define             vvL   vec<vL>
#define              vI   vec<int>
#define             vvI   vec<vI>
#define            vvvI   vec<vvI>
#define           vvvvI   vec<vvvI>
#define              vD   vec<db>
#define             vvD   vec<vD>
#define             vLL   vec<pLL>
#define             vLI   vec<pLI>
#define             vIL   vec<pIL>
#define             vII   vec<pII>
#define            vvII   vec<vII>
#define              vS   vec<string>
#define             vvS   vec<vS>
#define              vB   vec<bool>
#define             vvB   vec<vB>
#define            umap   unordered_map
#define          gphash   gp_hash_table
#define            mset   multiset
#define            pque   priority_queue
#define          all(a)   a.begin(), a.end()
#define         rall(a)   a.rbegin(), a.rend()
#define       stt(a, n)   a.begin(), a.begin() + n
#define       stf(a, n)   a.begin() + n, a.end()
#define              eb   emplace_back
#define              pb   push_back
#define              pf   push_front
#define            popb   pop_back
#define            popf   pop_front
#define             ins   insert
#define             asg   assign
#define             rev   reverse
#define              fi   first
#define              se   second
#define              th   third
#define              ub   upper_bound
#define              lb   lower_bound
#define             ite   iterator
#define           fs(n)   fixed << setprecision(n)

using         namespace   std;
using         namespace   __gnu_pbds;

const ll          llINF = 1e18;
const int        intINF = 1e9;
const ll            MOD = 1e9 + 7;
const ll            LIM = 1e6;

template<   class T   >   
using       ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define            oset   ordered_set

template<     class A, 
              class B, 
              class C >   struct triple {
    A fi; B se; C th;

    triple() {}
    triple(A a,B b,C c) : fi(a), se(b), th(c) {}
};
#define            tIII   triple<int, int, int>
#define            tLLL   triple<ll, ll, ll>
#define            vIII   vec<tIII>
#define           vvIII   vec<vIII>
#define            vLLL   vec<tLLL>

mt19937                   Rand(chrono::high_resolution_clock::now().time_since_epoch().count());

vI          prime, lpf;
void  primeSieve(int n)   { prime.asg(1, 2); lpf.asg(n + 1, 2); lpf[0] = lpf[1] = 1;
                            for (int i = 3; i <= n; i += 2) { if (lpf[i] == 2) { lpf[i] = i; prime.pb(i); } 
                            for (int j = 0; j < prime.size() && i * prime[j] <= n && prime[j] <= lpf[i]; ++ j) lpf[i * prime[j]] = prime[j]; 
                          } }
vvI                dvs;
void    dvsSieve(int n)   { dvs.asg(n + 1, vI());
                            for (int i = 1; i <= n; ++ i) {
                            for (int j = i; j <= n; j += i) 
                            dvs[j].pb(i);  
                          } }

template<   class T   >   bool maximize(T &a, T b) { if (b > a) return a = b, 1; return 0; }
template<   class T   >   bool minimize(T &a, T b) { if (b < a) return a = b, 1; return 0; }

ll      gcd(ll a, ll b)   { return b ? gcd(b, a % b) : a; }
ll      lcm(ll a, ll b)   { return a / gcd(a, b) * b; }

ll  fastPow(ll n, ll p,
            ll m = MOD)   { ll r = 1; for (n %= m; p; p >>= 1) { if (p & 1) (r *= n) %= m; (n *= n) %= m; } return r; }
ll         invMod(ll n, 
            ll m = MOD)   { return fastPow(n, m - 2, m); }

ll          mask(int i)   { return 1LL << i; }
bool   bit(ll n, int i)   { return n >> i & 1LL; }
#define        popcount   __builtin_popcountll
#define             clz   __builtin_clzll
#define             ctz   __builtin_ctzll

//__________________________________________________________________________________________________//

void init() {}

void solve() {
    int N; cin >> N;
    if (N & 1) { cout << 0; return; }
    string S; cin >> S;

    /*
    if (N <= 100) {
        vvI DP;
        int res = 0;
        for (int i = 0; i < N; ++ i) for (int j = i; j < N; ++ j) {
            string T = S;
            for (int k = i; k <= j; ++ k) {
                if (T[k] == '(') T[k] = ')';
                else if (T[k] == ')') T[k] = '(';
            }
            DP.asg(N + 1, vI(N + 1)); DP[0][0] = 1;
            for (int x = 0; x < N; ++ x) for (int y = 0; y <= x + 1; ++ y) {
                if (T[x] == '(' && y > 0) DP[x + 1][y] = DP[x][y - 1];
                if (T[x] == ')' && y < N) DP[x + 1][y] = DP[x][y + 1];
                if (T[x] == 'x') {
                    if (y > 0) (DP[x + 1][y] += DP[x][y - 1]) %= MOD;
                    if (y < N) (DP[x + 1][y] += DP[x][y + 1]) %= MOD;
                }
            }
            (res += DP[N][0]) %= MOD;
        }
        cout << res;
        return;
    }
    */

    vvvI DP(2, vvI(3, vI(N + 1))); 
    DP[0][0][0] = 1; bool f = 1;
    for (int i = 1; i <= N; ++ i, f = !f) {
        DP[f].asg(3, vI(N + 1));
        for (int j = 0; j <= i; ++ j) {
            if (S[i - 1] == '(') {
                if (j > 0) DP[f][0][j] = DP[!f][0][j - 1];
                if (j < N) DP[f][1][j] = (DP[!f][1][j + 1] + DP[!f][0][j + 1]) % MOD;
                if (j > 0) DP[f][2][j] = (DP[!f][2][j - 1] + DP[!f][1][j - 1]) % MOD;
            }
            if (S[i - 1] == ')') {
                if (j < N) DP[f][0][j] = DP[!f][0][j + 1];
                if (j > 0) DP[f][1][j] = (DP[!f][1][j - 1] + DP[!f][0][j - 1]) % MOD;
                if (j < N) DP[f][2][j] = (DP[!f][2][j + 1] + DP[!f][1][j + 1]) % MOD;
            }
            if (S[i - 1] == 'x') {
                if (j > 0) {
                    DP[f][0][j] = DP[!f][0][j - 1];
                    DP[f][1][j] = (DP[!f][1][j - 1] + DP[!f][0][j - 1]) % MOD;
                    DP[f][2][j] = (DP[!f][2][j - 1] + DP[!f][1][j - 1]) % MOD;
                }
                if (j < N) {
                    (DP[f][0][j] += DP[!f][0][j + 1]) %= MOD;
                    (DP[f][1][j] += (DP[!f][1][j + 1] + DP[!f][0][j + 1]) % MOD) %= MOD;
                    (DP[f][2][j] += (DP[!f][2][j + 1] + DP[!f][1][j + 1]) % MOD) %= MOD;
                }
            }
        }
    }

    cout << (DP[!f][1][0] + DP[!f][2][0]) % MOD;
}

signed main() {

    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    init();

    int tests = 1;
    //cin >> tests;

    while (tests --) solve();

    return 0;
}

Compilation message (stderr)

securitygate.cpp: In function 'void primeSieve(int)':
securitygate.cpp:87:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                             for (int j = 0; j < prime.size() && i * prime[j] <= n && prime[j] <= lpf[i]; ++ j) lpf[i * prime[j]] = prime[j];
      |                                             ~~^~~~~~~~~~~~~~
securitygate.cpp: In function 'int main()':
securitygate.cpp:184:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
securitygate.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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