Submission #537557

#	Time	Username	Problem	Language	Result	Execution time	Memory
537557		maomao90	Security Gate (JOI18_security_gate)	C++17	12 / 100	5094 ms	324 KiB

securitygate

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 305
#define MOD 1000000007

int n;
string s;
int ans;

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n;
    cin >> s;
    int x = 0;
    REP (i, 0, n) {
        if (s[i] == 'x') x++;
    }
    REP (m, 0, 1 << x) {
        int j = 0;
        vi v(n, 0);
        int sm = 0;
        REP (i, 0, n) {
            char c = s[i];
            if (c == 'x') {
                c = (m >> j & 1) ? '(' : ')';
                j++;
            }
            v[i] = c == '(' ? 1 : -1;
            sm += v[i];
        }
        if (sm % 2 == 1) continue;
        bool pos = 0;
        REP (i, 0, n) {
            REP (j, i - 1, n) {
                int sm = 0;
                REP (k, 0, n) {
                    int x = v[k];
                    if (k >= i && k <= j) {
                        x *= -1;
                    }
                    sm += x;
                    if (sm < 0) {
                        break;
                    }
                }
                if (sm == 0) {
                    pos = 1;
                    break;
                }
            }
            if (pos) {
                break;
            }
        }
        if (pos) {
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

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