QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#687673#9463. 基础 ABC 练习题HuTao100 ✓694ms7628kbC++143.3kb2024-10-29 20:24:472024-10-29 20:24:48

Judging History

你现在查看的是最新测评结果

  • [2024-10-29 20:24:48]
  • 评测
  • 测评结果:100
  • 用时:694ms
  • 内存:7628kb
  • [2024-10-29 20:24:47]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 62;

int n;
char s0[N], s1[N];
char s[N * 3];
unsigned f[N][N][N][4];

inline void Work()
{
    scanf("%d%s%s%s", &n, s0, s1, s + 1);
    if(n != 60) return void(puts("-1"));
    for(int i = 0; i <= n; i ++ ) s0[i] ^= 48, s1[i] ^= 48;
    unsigned ans = 0;
    for(int x = 0; x <= n; x ++ )
        for(int y = 0; y <= n - x; y ++ )
        {
            if(!s0[x] || !s1[y]) continue;
            int z = n - x - y;
            // printf("*%d %d %d\n", x, y, z);
            f[0][0][0][0] = f[0][0][0][1] = f[0][0][0][2] = f[0][0][0][3] = 0;
            f[0][0][0][!x << 1 | !y] = 1;
            int p = x - 1, q = y - 1;
            while(p >= 0 && !s0[p]) p -- ;
            while(q >= 0 && !s1[q]) q -- ;
            for(int i = 0; i <= n; i ++ )
                for(int j = 0; j <= min(n, i + y); j ++ )
                    for(int k = max(!i & !j, i - x); k <= min(n, j + z); k ++ )
                    {
                        f[i][j][k][0] = f[i][j][k][1] = f[i][j][k][2] = f[i][j][k][3] = 0;
                        if(i && (s[i + j + k] == 'A' || s[i + j + k] == '?'))
                        {
                            f[i][j][k][0] += f[i - 1][j][k][0];
                            f[i][j][k][1] += f[i - 1][j][k][1];
                            f[i][j][k][2] += f[i - 1][j][k][2];
                            f[i][j][k][3] += f[i - 1][j][k][3];
                        }
                        if(j && (s[i + j + k] == 'B' || s[i + j + k] == '?'))
                        {
                            f[i][j][k][0] += f[i][j - 1][k][0];
                            f[i][j][k][1] += f[i][j - 1][k][1];
                            f[i][j][k][2] += f[i][j - 1][k][2];
                            f[i][j][k][3] += f[i][j - 1][k][3];
                        }
                        if(k && (s[i + j + k] == 'C' || s[i + j + k] == '?'))
                        {
                            f[i][j][k][0] += f[i][j][k - 1][0];
                            f[i][j][k][1] += f[i][j][k - 1][1];
                            f[i][j][k][2] += f[i][j][k - 1][2];
                            f[i][j][k][3] += f[i][j][k - 1][3];
                        }
                        if(i - k > p)
                        {
                            f[i][j][k][2] += f[i][j][k][0];
                            f[i][j][k][3] += f[i][j][k][1];
                            f[i][j][k][0] = f[i][j][k][1] = 0;
                        }
                        if(j - i > q)
                        {
                            f[i][j][k][1] += f[i][j][k][0];
                            f[i][j][k][3] += f[i][j][k][2];
                            f[i][j][k][0] = f[i][j][k][2] = 0;
                        }
                        // printf("!%d %d %d\n", i, j, k);
                    }
            ans += f[n][n][n][3];
            for(int i = 0; i <= n; i ++ )
                for(int j = 0; j <= min(n, i + y); j ++ )
                    for(int k = max(!i & !j, i - x); k <= min(n, j + z); k ++ )
                        f[i][j][k][0] = f[i][j][k][1] = f[i][j][k][2] = f[i][j][k][3] = 0;
        }
    printf("%u\n", ans);
}

int main()
{
    int T;
    scanf("%d%*d", &T);
    while(T -- ) Work();
    return 0;
}

详细

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 649ms
memory: 7572kb

input:

60 1
1
11
11
ABC
2
111
111
CABABC
3
1111
1111
CAABBCBAC
4
11111
11111
BACBBACBACAC
5
111111
111111
CABCCBBAABCCBAA
6
1111111
1111111
ABABABCACBCBCCACBA
7
11111111
11111111
BCAABACBBCBBABCCAACAC
8
111111111
111111111
CCBCBBBCAABCBCAAAAACBCBA
9
1111111111
1111111111
CCCCACABCBABAABCCAABABBCBBA
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #2:

score: 20
Accepted
time: 643ms
memory: 7616kb

input:

60 1
1
11
11
CBA
2
111
111
BACACB
3
1111
1111
BCBCACABA
4
11111
11111
CCBACABBBCAA
5
111111
111111
BCACBBABBCCAACA
6
1111111
1111111
BBCBACCAACBCBCAABA
7
11111111
11111111
ACBCCBBAABAABCACCACBB
8
111111111
111111111
BAACACBACCCBAACCBABABBCB
9
1111111111
1111111111
BABCBCAAAAABBCCCACBCBBABACC
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #3:

score: 20
Accepted
time: 620ms
memory: 7556kb

input:

60 1
1
11
11
BCA
2
111
111
BCABCA
3
1111
1111
CBACCAABB
4
11111
11111
BACBCBBCCAAA
5
111111
111111
BCCCBABACCBABAA
6
1111111
1111111
ACAACBABABBCACBCCB
7
11111111
11111111
BBBCABCCCAABCACBACAAB
8
111111111
111111111
ACCACAABACBAABBCBCBBACBC
9
1111111111
1111111111
BCCBACBBACCCBCCAABAACABAABB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #4:

score: 20
Accepted
time: 622ms
memory: 7500kb

input:

60 1
1
11
11
BCA
2
111
111
ACABCB
3
1111
1111
BABCABCCA
4
11111
11111
CCABACABBACB
5
111111
111111
ABBBCBBCACCAACA
6
1111111
1111111
CACBABCABCCBABAACB
7
11111111
11111111
BACBCABACBBCCCBAAACAB
8
111111111
111111111
CABABBCAACABCBACBABACBCC
9
1111111111
1111111111
BCBAACBABABCBACBABABCCACACC
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #5:

score: 20
Accepted
time: 604ms
memory: 7616kb

input:

60 1
1
11
11
ABC
2
111
111
BBCACA
3
1111
1111
ACBBCBAAC
4
11111
11111
ABACACCCABBB
5
111111
111111
ACCCCCAAABABBBB
6
1111111
1111111
ABAABBBBCCCCCCAABA
7
11111111
11111111
ACBBBACCCCCCAABABBBAA
8
111111111
111111111
CAAABAAACCCCBBCBBBCACBAB
9
1111111111
1111111111
ABAAACBBCCCCCCCBAAABAACBBBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0

result:

ok Accepted!!!

Test #6:

score: 20
Accepted
time: 623ms
memory: 7624kb

input:

60 1
1
11
11
BCA
2
111
111
ACCBAB
3
1111
1111
BACCACBBA
4
11111
11111
AAABBCBCBACC
5
111111
111111
AABBBBCCBCCAACA
6
1111111
1111111
AAACCBCCCAABACBBBB
7
11111111
11111111
AAACACCACBBAABBCBCCBB
8
111111111
111111111
AAACAAABBBBBBBCBACCCACCC
9
1111111111
1111111111
BBCCACCCACCACCBAABBAAAABBBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #7:

score: 20
Accepted
time: 590ms
memory: 7440kb

input:

60 1
1
11
11
BCA
2
111
111
ACCABB
3
1111
1111
CAABBBCAC
4
11111
11111
BBCCBCCABAAA
5
111111
111111
BAABBBCCCCCAABA
6
1111111
1111111
AACACCCCBABBBCAABB
7
11111111
11111111
AACBBCBBBCCCCCAAABBAA
8
111111111
111111111
AAAABBCBBBBCBBCCCCCCAAAA
9
1111111111
1111111111
ABBBBBBBBCCBCAACCACAACCAAAC
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #8:

score: 20
Accepted
time: 587ms
memory: 7580kb

input:

60 1
1
11
11
ABC
2
111
111
AABCBC
3
1111
1111
ABAACBBCC
4
11111
11111
AABCCBBBCACA
5
111111
111111
AAACCABBBACBCCB
6
1111111
1111111
AABBBBBBCCACAACACC
7
11111111
11111111
AAAABBBBBBCCACCCCCBAA
8
111111111
111111111
ACCBABBABBBBBCCCACCCAAAA
9
1111111111
1111111111
BAAAABCCCCCCCBBAABAACABCBBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0

result:

ok Accepted!!!

Test #9:

score: 20
Accepted
time: 594ms
memory: 7476kb

input:

60 1
1
11
11
CAB
2
111
111
CCAABB
3
1111
1111
ACCCABBAB
4
11111
11111
AAABBBBCCACC
5
111111
111111
BCACCCCBAAAABBB
6
1111111
1111111
CAAACABABACCCBCBBB
7
11111111
11111111
ACAAACBCCCCBCAABBABBB
8
111111111
111111111
ACCAACACCCCCABABAABBBBBB
9
1111111111
1111111111
AACAAAAAACBCCBCBACBBBBBBCCC
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #10:

score: 20
Accepted
time: 591ms
memory: 7556kb

input:

60 1
1
11
11
BCA
2
111
111
ACACBB
3
1111
1111
AABCCCABB
4
11111
11111
CBCCCABABABA
5
111111
111111
ACACCCAABBCBABB
6
1111111
1111111
BACAAAACCBABCBCBCB
7
11111111
11111111
AAAAABBBBCCBBCCCCACAB
8
111111111
111111111
AACCCCCCABAAACAABCBBBBBB
9
1111111111
1111111111
AABAAAABCCCCABCCCABBCCABBBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #11:

score: 20
Accepted
time: 594ms
memory: 7436kb

input:

60 1
1
11
11
BCA
2
111
111
CBBCAA
3
1111
1111
AABABCCCB
4
11111
11111
BABCBBCAAACC
5
111111
111111
AAACBBBBBCAACCC
6
1111111
1111111
BBBBBCCCCCCAABAAAA
7
11111111
11111111
BAAAABAACCCABBCCBBBCC
8
111111111
111111111
ABABBBBBCBCCCACCCCAAABAA
9
1111111111
1111111111
AAAABBAABCABACCCACCCBBCBCBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #12:

score: 20
Accepted
time: 202ms
memory: 7616kb

input:

60 2
1
01
11
ABC
2
101
001
ACBABC
3
0011
1000
AAACBBCBC
4
11100
00100
BACABCABACBC
5
001101
110010
ACBABCCABBCCAAB
6
0101010
1000011
CABBAAACACBBCCABCB
7
10010111
10100111
CABAAACBBAACBCACBBBCC
8
100101000
100000110
BACBCACBBAABCCCABCBAACBA
9
1100010100
0111110011
CAABCBBABCACBCACABCABAACBBC
10
0001...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #13:

score: 20
Accepted
time: 190ms
memory: 7556kb

input:

60 2
1
01
01
CAB
2
011
101
ABCCBA
3
1111
0000
CBBAACCBA
4
00011
10011
BCCBCCABABAA
5
011111
111011
ACBBABCBCCAACBA
6
1011101
1101000
CBABBCACBAABABCACC
7
00001111
11010100
BCACAABCBBBCCABABCACA
8
110110100
010010100
ABAABCABCABAACCCCBBBBCCA
9
0000111111
1011100011
BAAABBCCABBBBCABACBACACCACC
10
0011...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #14:

score: 20
Accepted
time: 186ms
memory: 7492kb

input:

60 2
1
01
00
ABC
2
111
000
CAABBC
3
0101
0011
CAACBCBAB
4
11011
01001
CABBCAACBBCA
5
000010
010100
BCCCACAAACBBBBA
6
0011011
0011000
BCACCBAAAAABCBCBBC
7
11000001
11111111
AACBCABACCBBCABCCBAAB
8
111010100
111101010
CBABCACBABAACBABCCCBCAAB
9
1001111111
1011000111
CAABCACCABBBABBCACCABBCAACB
10
0011...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #15:

score: 20
Accepted
time: 198ms
memory: 7556kb

input:

60 2
1
00
10
BCA
2
110
000
BCAABC
3
0111
1001
CACAABBBC
4
10101
00000
ACCBCAABBACB
5
010001
100001
BBCBBAACCBACACA
6
0100101
0100010
CCAAAABCCAABBCBBBC
7
10010000
10010011
BCBCACBCBAAAABCABBCCA
8
001101111
110010111
CABACABCACBBABCBCABACABC
9
1000111100
1011101001
ACBCABABBCCBABCCAAACBBBACAC
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #16:

score: 20
Accepted
time: 83ms
memory: 7324kb

input:

60 2
1
10
11
CAB
2
110
100
AABBCC
3
0100
0110
CAABCBABC
4
01010
01000
BCBCABACBCAA
5
001110
100000
AAABBCCCABCBABC
6
1000000
1101100
ACCBACBCAABCAABBCB
7
11011110
01000000
AAAAABABBBCBBBACCCCCC
8
101000000
010000000
ACBABBCCCCCCCABAAABAABBB
9
1000000000
1000000000
CCCCCCCCCAABAAABABBBABBAABB
10
0111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #17:

score: 20
Accepted
time: 227ms
memory: 6952kb

input:

60 2
1
01
10
ABC
2
100
100
BCABCA
3
1000
1100
CABACCBAB
4
11001
10000
AABCBACABBCC
5
110000
101110
BACBCAABCABCBCA
6
1110000
1111100
AABBBBCABCCCCABAAC
7
10110000
11100000
AAACCABBCAABCBBABBCCC
8
001111100
011000000
ABAACAAAACABCBCBBBBBCCCC
9
0110000000
1111000000
AACBBACBBBCBCABACACBCAABCCA
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0

result:

ok Accepted!!!

Test #18:

score: 20
Accepted
time: 6ms
memory: 6856kb

input:

60 2
1
10
11
ABC
2
100
100
CABCAB
3
1000
1000
CCABCABAB
4
11100
10000
ACACBABCABCB
5
111101
100000
AABCABCBACABBCC
6
1000000
0100000
BCACCCCCABAAABBBBA
7
10101110
11000000
AAABBCBBCACCCABBAACBC
8
111110000
001100000
ACBBCBBCABACCACBBABAACCA
9
1110000000
1111110000
CAAACBCCBBAAABCCBACABACCBBB
10
1100...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #19:

score: 20
Accepted
time: 4ms
memory: 6708kb

input:

60 2
1
11
10
ABC
2
100
110
BCABCA
3
1000
1111
BBCBACCAA
4
10000
10011
BCABCABCABCA
5
011111
100000
AABCBCABACABCBC
6
1110000
1000000
CAAACCCBBBCAACABBB
7
10000000
01000000
ABBCACCCABBACABACBBAC
8
110100011
100000000
AABBCABCCAABBCABCABCABCC
9
1111011100
1100000000
AAACABBBBBCACABCCBABCACBCCA
10
0111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #20:

score: 20
Accepted
time: 133ms
memory: 7372kb

input:

60 2
1
10
10
CAB
2
110
100
ABCACB
3
1000
1000
CABCABCAB
4
10111
10000
CABCABCABCAB
5
100000
110000
BCCAABCBCABACAB
6
1000000
1111000
CCCABACAABBCABCABB
7
10000000
11000110
BBCBBBCCACCCBABAAACAA
8
110000000
100000000
AACBCABCABBACCABCBCAABBC
9
1000000000
1100000000
BBCCACACCCBBACBCCABABAAAABB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0

result:

ok Accepted!!!

Test #21:

score: 20
Accepted
time: 11ms
memory: 6548kb

input:

60 2
1
10
10
CAB
2
110
100
CABCAB
3
0111
1000
CABCABCAB
4
11010
11000
AAABBBCBACCC
5
110000
100000
ACBACABCBABCABC
6
1111000
1111000
AAABBBBBCACCCAABCC
7
11011100
01000000
AAAAACCBCBCBBBCACACBB
8
111000000
111010000
AAABBBBBCCCCCCCABACABABA
9
1011100010
1000000000
AAABAABAABBABBCCCCBCCCCBACB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Subtask #3:

score: 10
Accepted

Test #22:

score: 10
Accepted
time: 567ms
memory: 7564kb

input:

60 3
1
11
11
???
2
111
111
??????
3
1111
1111
?????????
4
11111
11111
????????????
5
111111
111111
???????????????
6
1111111
1111111
??????????????????
7
11111111
11111111
?????????????????????
8
111111111
111111111
????????????????????????
9
1111111111
1111111111
???????????????????????????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2103642368

result:

ok Accepted!!!

Subtask #4:

score: 20
Accepted

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Test #23:

score: 20
Accepted
time: 694ms
memory: 7492kb

input:

60 4
1
11
11
AC?
2
111
111
?ACAAA
3
1111
1111
AA?A?CCCC
4
11111
11111
??BBB?CBBACA
5
111111
111111
?CC?CCCAA?BCB??
6
1111111
1111111
?B?BBCCABBCBA?A?BC
7
11111111
11111111
AAA?B??C?CBABACCCA?AA
8
111111111
111111111
CBBB?AAC?B?A???BABAC?ACB
9
1111111111
1111111111
A?A?BAA?BCBC??ABBBBAAA?ACBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
967466944

result:

ok Accepted!!!

Test #24:

score: 20
Accepted
time: 668ms
memory: 7480kb

input:

60 4
1
11
11
CCA
2
111
111
BBAABC
3
1111
1111
?BACB?B?B
4
11111
11111
B??ACBBCBBA?
5
111111
111111
ABBBBC?CABCABA?
6
1111111
1111111
?ACAB?CAA?AB?C?AAC
7
11111111
11111111
?BAAA?BCAAA??AB?BABAC
8
111111111
111111111
BCBCC?ACACA?AAAC??BACACA
9
1111111111
1111111111
ACCCBCBAA?BABBA??BBBBACAA?A
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1537951906

result:

ok Accepted!!!

Test #25:

score: 20
Accepted
time: 687ms
memory: 7556kb

input:

60 4
1
11
11
A?B
2
111
111
BABBBB
3
1111
1111
?ABBABBCC
4
11111
11111
CBABBBCBABAB
5
111111
111111
AABCBA?CBBCCBBA
6
1111111
1111111
AB????CCBCC?BCBBB?
7
11111111
11111111
C?BBBC?BABCC?CC?A?BAC
8
111111111
111111111
CCAAACA?C?A??AAAABC?CAC?
9
1111111111
1111111111
BAABBBCA?A?BA?CA??CAAABBBAB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2235249070

result:

ok Accepted!!!

Test #26:

score: 20
Accepted
time: 680ms
memory: 7620kb

input:

60 4
1
11
11
???
2
111
111
???C??
3
1111
1111
?????????
4
11111
11111
?C???????AAA
5
111111
111111
???????????????
6
1111111
1111111
?????B???C?A?B?BC?
7
11111111
11111111
??????B??????A????C??
8
111111111
111111111
???????????C?CB?????????
9
1111111111
1111111111
??????B??CC?????B??C???????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2776680263

result:

ok Accepted!!!

Test #27:

score: 20
Accepted
time: 651ms
memory: 7552kb

input:

60 4
1
11
11
???
2
111
111
??????
3
1111
1111
?????????
4
11111
11111
???AC?????A?
5
111111
111111
????????C??A???
6
1111111
1111111
?A???????????????C
7
11111111
11111111
BC?C??????B??A?B?A???
8
111111111
111111111
???????C?????A??????????
9
1111111111
1111111111
???????????????????????????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
975867735

result:

ok Accepted!!!

Test #28:

score: 20
Accepted
time: 660ms
memory: 7432kb

input:

60 4
1
11
11
???
2
111
111
?B????
3
1111
1111
???????B?
4
11111
11111
????????????
5
111111
111111
?C??????????AA?
6
1111111
1111111
?????????????????A
7
11111111
11111111
?AA??????AB?CBC??????
8
111111111
111111111
????????????????????????
9
1111111111
1111111111
??A??????B?????A?????B????A
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3283652662

result:

ok Accepted!!!

Test #29:

score: 20
Accepted
time: 572ms
memory: 7576kb

input:

60 4
1
11
11
B?A
2
111
111
BACA??
3
1111
1111
???B?AB??
4
11111
11111
?BC?????A?B?
5
111111
111111
??BA??A?B??????
6
1111111
1111111
??????????????????
7
11111111
11111111
B?C?A????C???C???????
8
111111111
111111111
???B????????????????????
9
1111111111
1111111111
A?????????????????????????A
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2103642368

result:

ok Accepted!!!

Test #30:

score: 20
Accepted
time: 622ms
memory: 7576kb

input:

60 4
1
11
11
A?B
2
111
111
A?CBCA
3
1111
1111
?????????
4
11111
11111
C??C?????A??
5
111111
111111
???????A???????
6
1111111
1111111
?????????AC???C???
7
11111111
11111111
?????????????????A???
8
111111111
111111111
????????????????????????
9
1111111111
1111111111
??????????????A????????????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
776867426

result:

ok Accepted!!!

Test #31:

score: 20
Accepted
time: 580ms
memory: 7624kb

input:

60 4
1
11
11
?AA
2
111
111
A??BB?
3
1111
1111
??????B?C
4
11111
11111
????C???????
5
111111
111111
?B????B????????
6
1111111
1111111
?????????????A????
7
11111111
11111111
?B??A?????????A????BA
8
111111111
111111111
????????????????????????
9
1111111111
1111111111
??A????B?????AB???B????????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2103642368

result:

ok Accepted!!!

Test #32:

score: 20
Accepted
time: 622ms
memory: 7568kb

input:

60 4
1
11
11
A?C
2
111
111
?B?B??
3
1111
1111
?A????C??
4
11111
11111
???A????B???
5
111111
111111
??????C?A??B?B?
6
1111111
1111111
????C??????B?C??B?
7
11111111
11111111
???????????B????A????
8
111111111
111111111
??CAC????C??????????????
9
1111111111
1111111111
?????????C???????????????C?
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3736489762

result:

ok Accepted!!!

Subtask #5:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #33:

score: 30
Accepted
time: 145ms
memory: 7496kb

input:

60 5
1
10
11
BBB
2
110
111
?BAAAC
3
0011
1010
A?AC?A?C?
4
00000
10100
CACBBC?AABBC
5
000011
010001
?CAACC?BBCBCBBB
6
0100111
0011111
C??BAC??ACCCAC?BB?
7
00010001
10011110
??BCABCB???CAAAABBCC?
8
100100000
111010111
?BCACCBACCCCACABAA?CACA?
9
1100111101
0010011010
?BCBCBCCAC?ACBBCBAB?ABBC?B?
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
981665096

result:

ok Accepted!!!

Test #34:

score: 30
Accepted
time: 165ms
memory: 7488kb

input:

60 5
1
10
01
BC?
2
010
101
AA?CCB
3
1100
1011
CCACCAB?C
4
01011
00011
CBCCCCABCCCC
5
010110
111011
B?CB?AB?C?C?BCC
6
0100111
0011110
???C?AA?BBAB?CBABC
7
11100011
11000000
BCB?ACBBA?????BBBCA??
8
011000000
100101110
AB?ACCCBBBCCBBA?CAAA?AAB
9
0110101010
1001110110
BB?BBC?BAABA?AC?ABC???CCC??
10
0111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
927252812

result:

ok Accepted!!!

Test #35:

score: 30
Accepted
time: 202ms
memory: 7620kb

input:

60 5
1
01
00
C?C
2
100
111
ACA?AC
3
0000
1001
CCABA?BAA
4
11011
01100
BBB??AA??BB?
5
100001
001111
CCBCAAC????ACB?
6
0010010
0010110
?BCB??CAAABAABBAC?
7
10001011
01011101
BBCACCCACBBC?CCCCB?CB
8
111100000
000000111
?AAC?B?A?BC?AA?A??A?CBA?
9
0000000101
0011011101
BB?BCABAC?ACA??ABCC?ACB????
10
1101...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
754781458

result:

ok Accepted!!!

Test #36:

score: 30
Accepted
time: 423ms
memory: 7596kb

input:

60 5
1
11
11
??A
2
111
111
A????C
3
0111
1111
??B????C?
4
11111
11101
????????????
5
101111
111001
?B?B??????AC?C?
6
1111111
1111011
C???????B??CB?????
7
10111111
11111110
??????????????????BA?
8
111110100
011111011
????????????????????????
9
1100011111
1101011011
??AC????B??CB???C?C?????CC?
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
621310044

result:

ok Accepted!!!

Test #37:

score: 30
Accepted
time: 372ms
memory: 7564kb

input:

60 5
1
11
11
?B?
2
110
110
??????
3
1111
1111
???????C?
4
11101
10111
????A????A??
5
110111
010111
?????A??????C?B
6
0111111
1011110
??BB?????????B????
7
11111100
01110111
????????A??A?B????C??
8
011101101
111100011
?B???????B?A?C???B??????
9
1111101111
1111101111
??BC?????C?A?????C???????BB
10
1010...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
522683520

result:

ok Accepted!!!

Test #38:

score: 30
Accepted
time: 335ms
memory: 7576kb

input:

60 5
1
11
11
C??
2
111
101
??????
3
1111
1101
???C???C?
4
11110
11111
???????C????
5
011111
111101
????B????????B?
6
1011111
1111111
B????C?????AA????C
7
11110111
01111111
??????C??????????????
8
110111100
110011101
?????C????????????A?????
9
1110101111
1101111011
?????B????C???C???????CA???
10
1011...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2768886394

result:

ok Accepted!!!

Test #39:

score: 30
Accepted
time: 555ms
memory: 7552kb

input:

60 5
1
10
00
BAA
2
111
111
CBC??A
3
0000
0000
A??BA??BA
4
00100
11111
????????????
5
111111
000010
??A?????????AA?
6
0000110
0100010
B??????????C???C??
7
01011000
11111111
?????A???????????????
8
101000101
100111101
?B?????????????????A????
9
1011010011
1111111111
????????C??C?B????AC???????
10
1101...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2198024491

result:

ok Accepted!!!

Test #40:

score: 30
Accepted
time: 551ms
memory: 7628kb

input:

60 5
1
00
00
CBA
2
111
111
BCB?CC
3
0110
1011
?A?B?B??C
4
10111
00000
????A????BB?
5
100000
111110
????????B??????
6
1011111
0100101
C????C??????ACA???
7
11111111
11111101
????????????????C????
8
101000101
110001010
??????????A???C??C?A????
9
1000101111
1111101111
????B?C??CC?????????????C??
10
1011...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3444482677

result:

ok Accepted!!!

Test #41:

score: 30
Accepted
time: 572ms
memory: 7628kb

input:

60 5
1
10
01
AAB
2
100
110
??????
3
1111
1111
?A?AB???C
4
01100
11110
BA?A?A??C???
5
110000
111101
?????????C?C?A?
6
0001010
0100011
A??B????????B???A?
7
00101010
11111111
????????????????????B
8
101111011
011111111
?B???????????C?????C?A??
9
1101110111
0111111111
?????C?????AB??????????A???
10
1011...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2103642368

result:

ok Accepted!!!

Test #42:

score: 30
Accepted
time: 595ms
memory: 7436kb

input:

60 5
1
10
10
CCC
2
110
000
CA?CA?
3
0101
1100
BBBB??B??
4
10000
00000
C??????AA???
5
010100
000001
????C??B??C????
6
0011111
0110101
????????????A?A???
7
10111100
11111011
?????????????????????
8
010111001
110010010
???????????????B???A????
9
1111100111
1101111110
???????????????????????????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2853696586

result:

ok Accepted!!!

Extra Test:

score: 0
Extra Test Passed