답안 #16234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16234	2015-08-18T11:08:25 Z	eaststar	백신 (KOI13_vaccine)	C++14	24 / 24	456 ms	1528 KB

vaccine

#include <stdio.h>
int a[110][1010],l[110],p[1010],pi[1010],chk[1010],k;
void ff(){
    int i=0,j=-1;
    pi[0]=-1;
    while(i<k){
        if(j<0||p[i]==p[j])++i,++j,pi[i]=j;
        else j=pi[j];
    }
}
int kmp(int n){
    int i=0,j=-1;
    while(i<l[n]){
        if(j<0||a[n][i]==p[j])++i,++j;
        else j=pi[j];
        if(j>=k)return 1;
    }
    return 0;
}
int main(){
    int i,j,n,s;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i){
        scanf("%d",l+i);
        for(j=0;j<l[i];++j)scanf("%d",a[i]+j);
    }
    for(i=0;i<l[1]-k;++i){
        for(j=0;j<k;++j)p[j]=a[1][i+j];
        ff();
        s=1;
        for(j=2;j<=n;++j)chk[j]=0;
        for(j=2;j<=n;++j)if(kmp(j))++s,chk[j]=1;
        for(j=0;j<k;++j)p[k-j-1]=a[1][i+j];
        ff();
        for(j=2;j<=n;++j)if(!chk[j]&&kmp(j))++s;
        if(s==n)break;
    }
    if(i<l[1]-k)puts("YES");
    else puts("NO");
    return 0;
}

Subtask #1

2.64 / 2.64

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1528 KB	Output is correct
2	Correct	0 ms	1528 KB	Output is correct
3	Correct	0 ms	1528 KB	Output is correct
4	Correct	0 ms	1528 KB	Output is correct
5	Correct	0 ms	1528 KB	Output is correct
6	Correct	0 ms	1528 KB	Output is correct
7	Correct	0 ms	1528 KB	Output is correct
8	Correct	0 ms	1528 KB	Output is correct
9	Correct	0 ms	1528 KB	Output is correct
10	Correct	0 ms	1528 KB	Output is correct

Subtask #2

3.12 / 3.12

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1528 KB	Output is correct
2	Correct	0 ms	1528 KB	Output is correct
3	Correct	0 ms	1528 KB	Output is correct
4	Correct	0 ms	1528 KB	Output is correct
5	Correct	0 ms	1528 KB	Output is correct
6	Correct	0 ms	1528 KB	Output is correct
7	Correct	0 ms	1528 KB	Output is correct
8	Correct	0 ms	1528 KB	Output is correct
9	Correct	0 ms	1528 KB	Output is correct
10	Correct	0 ms	1528 KB	Output is correct

Subtask #3

3.6 / 3.6

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1528 KB	Output is correct
2	Correct	0 ms	1528 KB	Output is correct
3	Correct	0 ms	1528 KB	Output is correct
4	Correct	0 ms	1528 KB	Output is correct
5	Correct	0 ms	1528 KB	Output is correct
6	Correct	0 ms	1528 KB	Output is correct
7	Correct	0 ms	1528 KB	Output is correct
8	Correct	0 ms	1528 KB	Output is correct
9	Correct	0 ms	1528 KB	Output is correct
10	Correct	4 ms	1528 KB	Output is correct

Subtask #4

4.32 / 4.32

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1528 KB	Output is correct
2	Correct	0 ms	1528 KB	Output is correct
3	Correct	3 ms	1528 KB	Output is correct
4	Correct	0 ms	1528 KB	Output is correct
5	Correct	0 ms	1528 KB	Output is correct
6	Correct	3 ms	1528 KB	Output is correct
7	Correct	2 ms	1528 KB	Output is correct
8	Correct	0 ms	1528 KB	Output is correct
9	Correct	2 ms	1528 KB	Output is correct
10	Correct	2 ms	1528 KB	Output is correct

Subtask #5

4.8 / 4.8

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	1528 KB	Output is correct
2	Correct	10 ms	1528 KB	Output is correct
3	Correct	4 ms	1528 KB	Output is correct
4	Correct	128 ms	1528 KB	Output is correct
5	Correct	9 ms	1528 KB	Output is correct
6	Correct	33 ms	1528 KB	Output is correct
7	Correct	44 ms	1528 KB	Output is correct
8	Correct	8 ms	1528 KB	Output is correct
9	Correct	12 ms	1528 KB	Output is correct
10	Correct	325 ms	1528 KB	Output is correct

Subtask #6

5.52 / 5.52

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	1528 KB	Output is correct
2	Correct	123 ms	1528 KB	Output is correct
3	Correct	85 ms	1528 KB	Output is correct
4	Correct	94 ms	1528 KB	Output is correct
5	Correct	189 ms	1528 KB	Output is correct
6	Correct	270 ms	1528 KB	Output is correct
7	Correct	181 ms	1528 KB	Output is correct
8	Correct	10 ms	1528 KB	Output is correct
9	Correct	456 ms	1528 KB	Output is correct
10	Correct	445 ms	1528 KB	Output is correct