CSES - COCI 2007/2008 #1

CSES - COCI 2007/2008 #1 - Results

Submission details
Task:	Zapis
Sender:	henrikaalto
Submission time:	2019-07-29 15:44:35 +0300
Language:	C++ (C++17)
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0

Test results
test	verdict	time
#1	WRONG ANSWER	0.01 s	details
#2	WRONG ANSWER	0.01 s	details
#3	WRONG ANSWER	0.01 s	details
#4	WRONG ANSWER	0.02 s	details
#5	WRONG ANSWER	0.07 s	details
#6	WRONG ANSWER	0.21 s	details
#7	RUNTIME ERROR	0.05 s	details
#8	RUNTIME ERROR	0.02 s	details
#9	RUNTIME ERROR	0.03 s	details
#10	RUNTIME ERROR	0.02 s	details

Code

// :E
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
using ii=long long;


const int N = 205;


int dp[2][N][N][N]; // (, [, {
int pd[2][N][N][N];

int z = 0;

const int mod = 1e5;

int lol = 0;

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    if (s[0] == '?') {
        dp[z][1][0][0] = 1;
        dp[z][0][1][0] = 1;
        dp[z][0][0][1] = 1;
    }
    if (s[0] == '(') {
        dp[z][1][0][0] = 1;
    }
    if (s[0] == '[') {
        dp[z][0][1][0] = 1;
    }
    if (s[0] == '{') {
        dp[z][0][0][1] = 1;
    }
        for (int j = 0; j < n; ++j) {
            for (int h = 0; h < n; ++h) {
                for (int k = 0; k < n; ++k) {
                    //printf("dp[%d][%d][%d] = %d\n", j, h, k, dp[z][j][h][k]);
                }
            }
        }
        //printf("\n\n");
    for (int i = 1; i < n; ++i) {
        z = !z;
        for (int j = 0; j < n; ++j) {
            for (int h = 0; h < n; ++h) {
                for (int k = 0; k < n; ++k) {
                    dp[z][j][h][k] = 0;
                    pd[z][j][h][k] = 0;
                }
            }
        }
        if (s[i] == '?') {
            for (int j = 0; j < n; ++j) {
                for (int h = 0; h < n; ++h) {
                    for (int k = 0; k < n; ++k) {
                        if (j > 0) {
                            dp[z][j][h][k] += dp[!z][j - 1][h][k];
                            //printf("dp[%d][%d][%d] += dp[%d][%d][%d]\n", j, h, k, j - 1, h, k);
                            pd[z][j][h][k] |= pd[!z][j - 1][h][k];
                        }
                        if (h > 0) {
                            dp[z][j][h][k] += dp[!z][j][h - 1][k];
                            //printf("dp[%d][%d][%d] += dp[%d][%d][%d]\n", j, h, k, j, h - 1, k);
                            pd[z][j][h][k] |= pd[!z][j][h - 1][k];
                        }
                        if (k > 0) {
                            dp[z][j][h][k] += dp[!z][j][h][k - 1];
                            //printf("dp[%d][%d][%d] += dp[%d][%d][%d]\n", j, h, k, j, h, k - 1);
                            pd[z][j][h][k] |= pd[!z][j][h][k - 1];
                        }
                        dp[z][j][h][k] += dp[!z][j + 1][h][k];
                        //printf("dp[%d][%d][%d] += dp[%d][%d][%d]\n", j, h, k, j + 1, h, k);
                        pd[z][j][h][k] |= pd[!z][j + 1][h][k];
                        dp[z][j][h][k] += dp[!z][j][h + 1][k];
                        //printf("dp[%d][%d][%d] += dp[%d][%d][%d]\n", j, h, k, j, h+1, k);
                        pd[z][j][h][k] |= pd[!z][j][h + 1][k];
                        dp[z][j][h][k] += dp[!z][j][h][k + 1];
                        //printf("dp[%d][%d][%d] += dp[%d][%d][%d]\n", j, h, k, j, h, k+1);
                        pd[z][j][h][k] |= pd[!z][j][h][k + 1];
                        if (dp[z][j][h][k] >= mod) {
                            pd[z][j][h][k] = 1;
                        }
                        dp[z][j][h][k] %= mod;
                    }
                }
            }
        }
        else {
            for (int j = 0; j < n; ++j) {
                for (int h = 0; h < n; ++h) {
                    for (int k = 0; k < n; ++k) {
                        if (s[i] == ')') {
                            dp[z][j][h][k] += dp[!z][j + 1][k][h];
                            pd[z][j][h][k] |= pd[!z][j + 1][k][h];
                        }
                        if (s[i] == '(') {
                            if (j > 0) {
                                dp[z][j][h][k] += dp[!z][j - 1][k][h];
                                pd[z][j][h][k] |= pd[!z][j - 1][k][h];
                            }
                        }
                        if (s[i] == ']') {
                            dp[z][j][h][k] += dp[!z][j][k + 1][h];
                            pd[z][j][h][k] |= pd[!z][j][k + 1][h];
                        }
                        if (s[i] == '[') {
                            if (k > 0) {
                                dp[z][j][h][k] += dp[!z][j][k - 1][h];
                                pd[z][j][h][k] |= pd[!z][j][k - 1][h];
                            }
                        }
                        if (s[i] == '}') {
                            dp[z][j][h][k] += dp[!z][j][k][h + 1];
                            pd[z][j][h][k] |= pd[!z][j][k][h + 1];
                        }
                        if (s[i] == '{') {
                            if (h > 0) {
                                dp[z][j][h][k] += dp[!z][j][k][h - 1];
                                pd[z][j][h][k] |= pd[!z][j][k][h - 1];
                            }
                        }
                        if (dp[z][j][h][k] >= mod) {
                            pd[z][j][h][k] = 1;
                        }
                        dp[z][j][h][k] %= mod;
                    }
                }
            }
        }
        for (int j = 0; j < n; ++j) {
            for (int h = 0; h < n; ++h) {
                for (int k = 0; k < n; ++k) {
                    //printf("dp[%d][%d][%d] = %d\n", j, h, k, dp[z][j][h][k]);
                }
            }
        }
        //printf("\n\n");
    }
    if (pd[z][0][0][0]) printf("%05d\n", dp[z][0][0][0]);
    else printf("%d\n", dp[z][0][0][0]);
}

Test details

Test 1

Verdict: WRONG ANSWER

input
`6 ??]{??` view save

correct output
`3` view save

user output
`9` view save

Test 2

Verdict: WRONG ANSWER

input
`10 ??)??{?]()` view save

correct output
`6` view save

user output
`40` view save

Test 3

Verdict: WRONG ANSWER

input
`20 ??[]]??{{??}}((?))??` view save

correct output
`186` view save

user output
`7572` view save

Test 4

Verdict: WRONG ANSWER

input
`30 (?([](??)[])?)]?()?{?[]([])???...` view save

correct output
`315` view save

user output
`2944` view save

Test 5

Verdict: WRONG ANSWER

input
`50 ([[[???[]?[??][??]?{??({})]??{...` view save

correct output
`00004` view save

user output
`24934` view save

Test 6

Verdict: WRONG ANSWER

input
`66 ???(??(??[?????[?][???(?{[????...` view save

correct output
`59479` view save

user output
`03748` view save

Test 7

Verdict: RUNTIME ERROR

input
`130 ((((?][]))([[[{[(?]}(?})??()]{...` view save

correct output
`2` view save

user output
(empty)

Test 8

Verdict: RUNTIME ERROR

input
`166 ?????????]??????)??{??????(???...` view save

correct output
`47279` view save

user output
(empty)

Test 9

Verdict: RUNTIME ERROR

input
`198 ?(?{?{?{{????}}????(??{}(?????...` view save

correct output
`68283` view save

user output
(empty)

Test 10

Verdict: RUNTIME ERROR

input
`200 [[[({(({[][]})[]){{?{{[]}}}()(...` view save

correct output
`24` view save

user output
(empty)

COCI 2007/2008 #1

Zapis

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Tasks

Submissions (henrikaalto)