oj.uz

Submission #814468

# Submission time Handle Problem Language Result Execution time Memory
814468 2023-08-08T07:42:31 Z 반딧불(#10119) Security Gate (JOI18_security_gate) C++17
0 / 100
 1 ms 276 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
char str[302];
char filled[302];
vector<int> blanks;
int ans;

int sum[302];
int spsR[302][7];
vector<int> vec[202];

bool goodString(){
    for(int i=1; i<=n; i++) sum[i] = sum[i-1] + (filled[i] == '(' ? 1 : -1), spsR[i][0] = sum[i];
    for(int d=1; d<7; d++) for(int i=1; i<=n; i++)
        spsR[i][d] = max(spsR[i][d-1], (i+(1<<(d-1))) <= n ? spsR[i+(1<<(d-1))][d-1] : INT_MIN);
    for(int i=0; i<=200; i++) vec[i].clear();
    if(*max_element(sum+1, sum+n+1) >= 0) return true;

    int minUntilNow = sum[n], pnt = 1;
    for(int i=n; i>=1; i--){
        minUntilNow = min(minUntilNow, sum[i]);
        if(minUntilNow < sum[n]){
            pnt = i+1;
            break;
        }
    }
    if(pnt == 1 && sum[n] == 0) return true;
    for(int i=pnt; i<=n; i++) vec[sum[i] + 100].push_back(i);

    for(int i=1; i<=n; i++){
        if(sum[i-1] < 0) break;
        int j = i-1; /// j���� ����
        int stype = (sum[n] + 2 * sum[i-1]) / 2 + 100;
        if(stype > 200 || stype < 0) continue;
        for(int d=6; d>=0; d--){
            if(spsR[j+1][d] <= sum[i-1] * 2) j += (1<<d);
        }
        int idx = upper_bound(vec[stype].begin(), vec[stype].end(), j) - vec[stype].begin() - 1;
        if(idx >= 0 && i <= vec[stype][idx] && vec[stype][idx] <= j) return true;
    }

    return false;
}

int main(){
    scanf("%d %s", &n, str+1);
    if(n%2){
        puts("0");
        return 0;
    }

    for(int i=1; i<=n; i++) if(str[i] == 'x') blanks.push_back(i);
    int k = (int)blanks.size();
    for(int d=0; d<(1<<k); d++){
        for(int i=1; i<=n; i++) filled[i] = str[i];
        for(int i=0; i<k; i++) filled[blanks[i]] = ((d>>i)&1) ? '(' : ')';
        if(goodString()) ans++;
    }
    printf("%d", ans);
}

Compilation message

securitygate.cpp: In function 'int main()':
securitygate.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d %s", &n, str+1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -