oj.uz

Submission #16234

# Submission time Handle Problem Language Result Execution time Memory
16234 2015-08-18T11:08:25 Z eaststar 백신 (KOI13_vaccine) C++14
24 / 24
 456 ms 1528 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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