QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#771029#9463. 基础 ABC 练习题miaomiaomiaowu69.7 2859ms4016kbC++205.9kb2024-11-22 08:51:522024-11-22 08:51:52

Judging History

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

  • [2024-11-22 08:51:52]
  • 评测
  • 测评结果:69.7
  • 用时:2859ms
  • 内存:4016kb
  • [2024-11-22 08:51:52]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef unsigned int ll;
typedef unsigned long long ull;
#define MP make_pair
#define pii pair<int,int>
const double PI=acos(-1.0);
template <class Miaowu>
inline void in(Miaowu &x){
    char c;x=0;bool f=0;
    for(c=getchar();c<'0'||c>'9';c=getchar())f|=c=='-';
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
    x=f?-x:x;
}
const int N=185;
char a[N],s1[N],s2[N];
int T,cas,n,nxta[N],nxtb[N];
ll dp[62][62][2][2],qwq[62][62][2][2];
long long F[62][62];
int main(){
    // freopen("qwq.in","r",stdin);
    // freopen("qwq.out","w",stdout);
    int B=59;
    for(cin>>T>>cas;T;T--){
        scanf("%d%s%s%s",&n,s1,s2,a+1);
        if(cas<=2){
            int n1=0,n2=0,n3=0,ca=0,cb=0,cc=0;
            for(int i=1;i<=3*n;i++){
                if(a[i]=='A')n1++,n2--;
                if(a[i]=='B')n2++,n3--;
                if(a[i]=='C')n3++,n1--;
                ca=max(ca,n1);
                cb=max(cb,n2);
                cc=max(cc,n3);
            }
            if(ca+cb+cc>n){
                puts("0");continue;
            }
            bool flag=0;
            for(int i=ca;i+cb+cc<=n;i++)if(s1[i]=='1'){
                for(int j=cb;i+j+cc<=n;j++){
                    if(s2[j]=='1')flag=1;
                }
            }
            puts(flag?"1":"0");
        }
        else{
            if(n!=B){
                puts("-1");continue;
            }
            memset(F,-1,sizeof F);
            nxta[n+1]=n+1,nxtb[n+1]=n+1;
            for(int i=n;i>=0;i--){
                if(s1[i]=='1')nxta[i]=i;
                else nxta[i]=nxta[i+1];
                if(s2[i]=='1')nxtb[i]=i;
                else nxtb[i]=nxtb[i+1];
            }
            ll ans=0;
            for(int la=0;la<=n;la++){
                for(int lb=0;la+lb<=n;lb++){
                    int lc=n-nxta[la]-nxtb[lb];
                    if(lc<0)continue;
                    if(la&&lb&&F[nxta[la]][nxtb[lb]]!=-1){
                        ans+=F[nxta[la]][nxtb[lb]];continue;
                    }
                    memset(dp,0,sizeof dp);
                    dp[0][0][la==0][lb==0]=1;
                    for(int i=1;i<=3*n;i++){
                        memcpy(qwq,dp,sizeof qwq);
                        memset(dp,0,sizeof dp);
                        if(a[i]=='A'){
                            for(register int j=0,l1=1-la;j<i&&j<n;++j,++l1)for(register int k=0,w=i-1-j;k<i&&k<=n&&w>=l1;++k,--w){
                                if(qwq[j][k][0][0])dp[j+1][k][j+1-w==la][0]+=qwq[j][k][0][0];
                                if(qwq[j][k][0][1])dp[j+1][k][j+1-w==la][1]+=qwq[j][k][0][1];
                                if(qwq[j][k][1][0])dp[j+1][k][1][0]+=qwq[j][k][1][0];
                                if(qwq[j][k][1][1])dp[j+1][k][1][1]+=qwq[j][k][1][1];
                            }
                        }
                        else if(a[i]=='B'){
                            for(register int j=0,l2=lb-1;j<i&&j<=n;++j,++l2)for(register int k=0;k<i&&k<n&&k<=l2;++k){
                                if(qwq[j][k][0][0])dp[j][k+1][0][k+1-j==lb]+=qwq[j][k][0][0];
                                if(qwq[j][k][0][1])dp[j][k+1][0][1]+=qwq[j][k][0][1];
                                if(qwq[j][k][1][0])dp[j][k+1][1][k+1-j==lb]+=qwq[j][k][1][0];
                                if(qwq[j][k][1][1])dp[j][k+1][1][1]+=qwq[j][k][1][1];
                            }
                        }
                        else if(a[i]=='C'){
                            for(register int j=0;j<i&&j<=n;++j)for(register int k=max(max(i-j-n,0),(i-j-lc+1)/2),w=i-1-j-k;k<i&&k<=n;++k,--w){
                                if(qwq[j][k][0][0])dp[j][k][0][0]+=qwq[j][k][0][0];
                                if(qwq[j][k][0][1])dp[j][k][0][1]+=qwq[j][k][0][1];
                                if(qwq[j][k][1][0])dp[j][k][1][0]+=qwq[j][k][1][0];
                                if(qwq[j][k][1][1])dp[j][k][1][1]+=qwq[j][k][1][1];
                            }
                        }
                        else{
                            for(register int j=0,l1=1-la,l2=lb-1;j<i&&j<=n;++j,++l1,++l2)for(register int k=0,w=i-1-j,l3=lc-1;k<i&&k<=n;++k,--w,++l3){
                                auto qaq=qwq[j][k];
                                if(qaq[0][0]){
                                    if(w>=l1)dp[j+1][k][w==l1][0]+=qaq[0][0];
                                    if(k<=l2)dp[j][k+1][0][k==l2]+=qaq[0][0];
                                    if(w<=l3)dp[j][k][0][0]+=qaq[0][0];
                                }
                                if(qaq[0][1]){
                                    if(w>=l1)dp[j+1][k][w==l1][1]+=qaq[0][1];
                                    if(k<=l2)dp[j][k+1][0][1]+=qaq[0][1];
                                    if(w<=l3)dp[j][k][0][1]+=qaq[0][1];
                                }
                                if(qaq[1][0]){
                                    if(w>=l1)dp[j+1][k][1][0]+=qaq[1][0];
                                    if(k<=l2)dp[j][k+1][1][k==l2]+=qaq[1][0];
                                    if(w<=l3)dp[j][k][1][0]+=qaq[1][0];
                                }
                                if(qaq[1][1]){
                                    if(w>=l1)dp[j+1][k][1][1]+=qaq[1][1];
                                    if(k<=l2)dp[j][k+1][1][1]+=qaq[1][1];
                                    if(w<=l3)dp[j][k][1][1]+=qaq[1][1];
                                }
                            }
                        }
                    }
                    ans+=dp[n][n][1][1];
                    F[nxta[la]][nxtb[lb]]=dp[n][n][1][1];
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

详细

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 3800kb

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: 0ms
memory: 3696kb

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:

0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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: 0ms
memory: 3840kb

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: 0ms
memory: 3740kb

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: 0ms
memory: 3660kb

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
0
0
0
1
1
0
1
1
1
1
1
0
1
1
1
0
0
0
0
1
1
1
0
1
1
1
1
1
0
0
1
0
1
0
1
0
0
0
1
0
0
0
1
1
0
1
0
0
1
0
1
0
1
0
0
0
1
0

result:

ok Accepted!!!

Test #6:

score: 20
Accepted
time: 0ms
memory: 3844kb

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
0
0
1
1
0
1
1
1
1
1
0
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
1
1
1
1
1
0
0
0
0
0
1
1
0
1
0
1
0
0
1
0
0
1
0
1
0
1
0
1
1
1
0
1

result:

ok Accepted!!!

Test #7:

score: 20
Accepted
time: 0ms
memory: 3868kb

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
0
1
1
1
0
1
1
1
1
0
1
1
0
1
1
0
0
1
0
1
1
0
1
1
0
0
0
0
1
1
0
0
1
0
1
1
1
0
0
1
0
1
1
1
1
1
0
0
1
1
0
0
0
0
0
1
0
1
1

result:

ok Accepted!!!

Test #8:

score: 20
Accepted
time: 0ms
memory: 3796kb

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
0
1
1
1
1
0
1
0
1
1
1
0
1
1
1
0
0
0
0
1
0
1
0
0
1
1
0
0
1
0
0
0
1
1
0
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
1
1
0
1
1
0

result:

ok Accepted!!!

Test #9:

score: 20
Accepted
time: 0ms
memory: 3656kb

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
0
1
1
0
0
0
0
1
1
0
0
1
1
0
1
1
1
1
0
0
1
0
1
1
0
1
1
1
1
0
0
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
0
0
0
0
0
0
0
1
1
1
1

result:

ok Accepted!!!

Test #10:

score: 20
Accepted
time: 0ms
memory: 3660kb

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
0
0
1
1
0
1
1
0
1
0
0
0
0
1
0
1
0
1
1
0
1
1
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
0
1
1
0
1
1

result:

ok Accepted!!!

Test #11:

score: 20
Accepted
time: 0ms
memory: 3736kb

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
0
0
0
0
1
0
1
0
0
1
0
1
0
1
1
1
0
1
0
0
0
1
1
1
1
0
1
1
0
1
0
0
0
0
1
0
1
0
0
1
1
1
1
1
1
0
1
0
1
1
1
0
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: 0ms
memory: 3796kb

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
0
0
1
1
0
1
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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: 0ms
memory: 3696kb

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:

0
0
0
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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: 0ms
memory: 3708kb

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:

0
0
0
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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: 0ms
memory: 3796kb

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:

0
0
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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: 0ms
memory: 3744kb

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
0
1
0
1
0
1
1
1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
0
1
1
1
0
0
1
1
1
1
0
1
0
1
1
1
1
0
1
1
0
0
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1

result:

ok Accepted!!!

Test #17:

score: 20
Accepted
time: 0ms
memory: 3860kb

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
0
0
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
0
0
0
1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
0
0
0

result:

ok Accepted!!!

Test #18:

score: 20
Accepted
time: 0ms
memory: 3656kb

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:

0
1
1
1
1
1
1
1
1
0
0
1
1
0
1
0
0
1
0
1
0
0
0
1
1
0
1
1
0
0
0
1
1
1
1
1
1
0
1
1
1
0
1
0
1
1
1
1
0
0
1
1
1
1
1
0
0
1
0
1

result:

ok Accepted!!!

Test #19:

score: 20
Accepted
time: 0ms
memory: 3740kb

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
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
1
0
0
1
1
1
1
0
0
1
0
1
1
0
1
1
1
0
0
1
1
1
1
0
1
0
0
1

result:

ok Accepted!!!

Test #20:

score: 20
Accepted
time: 0ms
memory: 3796kb

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
0
0
1
1
0
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
0
0
1
1
0
1
0
1
1
1
0
1
1
1
0
1
0
1
1
1
0
1
1
0

result:

ok Accepted!!!

Test #21:

score: 20
Accepted
time: 0ms
memory: 3796kb

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
0
0
1
0
1
0
1
1
1
1
0
1
1
1
0
0
1
1
1
1
0
0
1
1
0
1
0
0
1
1
0
1
1
0
0
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
0
0
1

result:

ok Accepted!!!

Subtask #3:

score: 9.9
Acceptable Answer

Test #22:

score: 9.9
Acceptable Answer
time: 2859ms
memory: 3928kb

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
2878195712
-1

result:

points 0.99 the max n you choose to answer is 59

Subtask #4:

score: 19.8
Acceptable Answer

Dependency #1:

100%
Accepted

Dependency #3:

99%
Acceptable Answer

Test #23:

score: 19.8
Acceptable Answer
time: 1951ms
memory: 4016kb

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
85150336
-1

result:

points 0.99 the max n you choose to answer is 59

Test #24:

score: 19.8
Acceptable Answer
time: 2044ms
memory: 3940kb

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
1656264096
-1

result:

points 0.99 the max n you choose to answer is 59

Test #25:

score: 19.8
Acceptable Answer
time: 1993ms
memory: 3924kb

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
4137046812
-1

result:

points 0.99 the max n you choose to answer is 59

Test #26:

score: 19.8
Acceptable Answer
time: 2613ms
memory: 3988kb

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
3636596937
-1

result:

points 0.99 the max n you choose to answer is 59

Test #27:

score: 19.8
Acceptable Answer
time: 2586ms
memory: 3884kb

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
3408532565
-1

result:

points 0.99 the max n you choose to answer is 59

Test #28:

score: 19.8
Acceptable Answer
time: 2530ms
memory: 3944kb

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
1610987457
-1

result:

points 0.99 the max n you choose to answer is 59

Test #29:

score: 19.8
Acceptable Answer
time: 2850ms
memory: 3932kb

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
2391054336
-1

result:

points 0.99 the max n you choose to answer is 59

Test #30:

score: 19.8
Acceptable Answer
time: 2858ms
memory: 4000kb

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
2878195712
-1

result:

points 0.99 the max n you choose to answer is 59

Test #31:

score: 19.8
Acceptable Answer
time: 2848ms
memory: 4004kb

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
2391054336
-1

result:

points 0.99 the max n you choose to answer is 59

Test #32:

score: 19.8
Acceptable Answer
time: 2853ms
memory: 3868kb

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
2878195712
-1

result:

points 0.99 the max n you choose to answer is 59

Subtask #5:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

99%
Acceptable Answer

Dependency #4:

99%
Acceptable Answer

Test #33:

score: 0
Wrong Answer
time: 619ms
memory: 3924kb

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
4135659535
-1

result:

wrong answer Your answer is wrong in testcase 59