Zapis

input/code.cpp: In function 'int match(char, char)':
input/code.cpp:43:15: warning: array subscript has type 'char' [-Wchar-subscripts]
     return q[a] == b;
               ^

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define debug(...) #__VA_ARGS__ << ": " << __VA_ARGS__
using ii=long long;
const ii mod=1e5;
struct mint {
    ii val;
    int over = 0;
    mint() {
        val = 0;
        over = 0;
    }
    mint(int x)
    {
        val = x;
    }
    mint &operator+=(const mint &b)
    {
        over |= b.over;
        if((val += b.val) >= mod) over = 1;
        val %= mod;
        return *this;
    }
    mint &operator*=(const mint &b)
    {
        over |= b.over;
        if((val *= b.val) >= mod) over = 1;
        val %= mod;
        return *this;
    }
    friend mint operator*(mint a, const mint &b)
    {
        return a *= b;
    }
};
int n;
char d[222],q[222];
mint dp[222][222][4];
int pd[222][222][4];
int match(char a, char b)
{
    return q[a] == b;
}
int fl(char a)
{
    return a == '(' || a == '[' || a == '{';
}
int fr(char a)
{
    return !fl(a);
}
mint hae(int a, int b, int c = 3)
{
    if (b & 1) return dp[a][b][c];
    if (b == 0) {
        dp[a][b][c].val = 1;
        return dp[a][b][c];
    }
    if (pd[a][b][c]) return dp[a][b][c];
    pd[a][b][c] = 1;
    mint &r = dp[a][b][c];
    if (c & 1) {
        mint x = hae(a + 1, b - 2);
        int ok = (d[a] == '?' && d[a + b - 1] != '?' && fr(d[a + b - 1]));
        ok |= (d[a] != '?' && d[a + b - 1] == '?' && fl(d[a]));
        ok |= (d[a] != '?' && d[a + b - 1] != '?' && match(d[a], d[a + b - 1]));
        if (ok) r = x;
        else if (d[a] == '?' && d[a + b - 1] == '?') r = mint(3) * x;
    }
    if (c & 2) {
        for (int i = 2; i < b; i += 2) {
            r += hae(a, i, 1) * hae(a + i, b - i, 2);
            r += hae(a, i, 1) * hae(a + i, b - i, 1);
        }
    }
    return dp[a][b][c];
}
int main()
{
    q['('] = ')';
    q['['] = ']';
    q['{'] = '}';
    cin >> n >> (d + 1);
    mint z = hae(1, n);
    printf((z.over ? "%05lld\n" : "%lld\n"), z.val);
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED