Submission #420478

#	Time	Username	Problem	Language	Result	Execution time	Memory
420478		ACmachine	Security Gate (JOI18_security_gate)	C++17	12 / 100	5041 ms	296 KiB

securitygate

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i-=(l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
typedef long long ll;
const int mod = (int)1e9 + 7;

int main(){
    int n; cin >> n;
    string s; cin >> s;
    int m = 0; 
    REP(i, s.length()){
        if(s[i] == 'x')
            m++;
    }
    int ans = 0;
    string ns;
    vector<int> min_suf(n + 1);
    vector<int> bal_suf(n + 1);
    auto check = [&](string s){
        int bal = 0;
        min_suf[n] = bal_suf[n] = 0;
        REPD(i, n - 1){
            if(s[i] == '(')
                bal++;
            else
                bal--;
            bal_suf[i] = bal;
            int up = (i == n - 1 ? 0 : min_suf[i + 1]);
            min_suf[i] = (s[i] == '(' ? 1 + up : up - 1);
            min_suf[i] = min(min_suf[i], 0);
        }
        bal = 0;
        if(min_suf[0] >= 0 && bal_suf[0] == 0) 
            return true;
        int mini = 0;
        REP(i, n){
            int nbal = bal;
            int nmini = mini;
            FOR(j, i, n, 1){
                nbal += (s[j] == '(' ? -1 : 1);
                nmini = min(nmini, nbal);
                if(nmini < 0) break;
                if(nbal + bal_suf[j + 1] == 0 && min_suf[j + 1] + nbal >= 0) 
                    return true;
            }
            bal += (s[i] == '(' ? 1 : -1);
            mini = min(mini, bal);  
            if(mini < 0)
                return false;
        }
        return false;
    };
    REP(mask, (1 << m)){
        ns = s; 
        int curr = 0;
        REP(j, n){
            if(ns[j] == 'x'){
                if(mask & (1 << curr))
                    ns[j] = '('; 
                else
                    ns[j] = ')';
                curr++;
            }
        }
        if(check(ns)){
            ans++;
        }
    }
    cout << ans << "\n";
}

Compilation message (stderr)

securitygate.cpp: In function 'int main()':
securitygate.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
securitygate.cpp:5:19: note: in expansion of macro 'FOR'
    5 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
securitygate.cpp:14:5: note: in expansion of macro 'REP'
   14 |     REP(i, s.length()){
      |     ^~~

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