CSES - COCI 2007/2008 #1 - Results
Submission details
Task:Zapis
Sender:henrikaalto
Submission time:2019-07-31 17:17:08 +0300
Language:C++17
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#50.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.02 sdetails
#10ACCEPTED0.02 sdetails

Compiler report

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

Code

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define debug(...) #__VA_ARGS__ << ": " << __VA_ARGS__
using ii=long long;
int n;
char d[222],q[222];
int dp[222][222][2], pd[222][222][2];
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);
}
int hae(int a, int b, int c = 3)
{
    if (b & 1) return dp[a][b][c] = 0;
    if (b == 0) return dp[a][b][c] = 1;
    if (pd[a][b][c]) return dp[a][b][c];
    pd[a][b][c] = 1;
    int r = 0;
    if (c & 1) {
        int 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 = 3 * x % (int) 1e5;
    }
    if (c & 2) {
        for (int i = 2; i < b; i += 2) {
            r += ((ii) hae(a, i, 1) * (ii) hae(a + i, b - i, 2)) % (ii) 1e5;
            r += ((ii) hae(a, i, 1) * (ii) hae(a + i, b - i, 1)) % (ii) 1e5;
            r %= (int) 1e5;
        }
    }
    return dp[a][b][c] = r;
}
int main()
{
    q['('] = ')';
    q['['] = ']';
    q['{'] = '}';
    cin >> n >> (d + 1);
    cout << hae(1, n) << "\n";
    return 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int c = 0; c < 2; ++c) if (dp[i][j][c]) {
                printf("dp[%d][%d][%d] = %d\n", i, j, c, dp[i][j][c]);
            }
        }
    }
}

Test details

Test 1

Verdict: ACCEPTED

input
6
??]{??

correct output
3

user output
3

Test 2

Verdict: ACCEPTED

input
10
??)??{?]()

correct output
6

user output
6

Test 3

Verdict: ACCEPTED

input
20
??[]]??{{??}}((?))??

correct output
186

user output
186

Test 4

Verdict: ACCEPTED

input
30
(?([](??)[])?)]?()?{?[]([])???...

correct output
315

user output
315

Test 5

Verdict:

input
50
([[[???[]?[??][??]?{??({})]??{...

correct output
00004

user output
4

Test 6

Verdict: ACCEPTED

input
66
???(??(??[?????[?][???(?{[????...

correct output
59479

user output
59479

Test 7

Verdict: ACCEPTED

input
130
((((?][]))([[[{[(?]}(?})??()]{...

correct output
2

user output
2

Test 8

Verdict: ACCEPTED

input
166
?????????]??????)??{??????(???...

correct output
47279

user output
47279

Test 9

Verdict: ACCEPTED

input
198
?(?{?{?{{????}}????(??{}(?????...

correct output
68283

user output
68283

Test 10

Verdict: ACCEPTED

input
200
[[[({(({[][]})[]){{?{{[]}}}()(...

correct output
24

user output
24