oj.uz

답안 #4945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4945 2014-01-23T13:13:56 Z hana5505 백신 (KOI13_vaccine) C++
24 / 24
 48 ms 1488 KB 
#include<stdio.h> 
int ar[101][1001]; 
int f[1001],size[101]; 
int go[1001],k,n; 
void make_kmp() 
{ 
    int i,j,s,cn=0; 
   
    go[0]=-1; 
    go[1]=0; 
    for(i=2;i<=k;i++){ 
        s=1;j=i;cn=0; 
        while(f[s]==f[j] && s<j){ 
            s++; 
            j++; 
            cn++; 
        } 
        go[j]=cn; 
    } 
} 
void reverse(int x) 
{ 
    int i,tmp; 
   
    for(i=1;i<=size[x]/2;i++){ 
        tmp=ar[x][i]; 
        ar[x][i]=ar[x][size[x]-i+1]; 
        ar[x][size[x]-i+1]=tmp; 
    } 
} 
int find() 
{ 
    int i,j,l,ll,cn=0,t=0; 
   
    for(i=2;i<=n;i++){ 
        t=0; 
        for(j=1;j<=size[i];j++){ 
            l=j; 
            ll=1; 
            cn=0; 
            while(ar[i][l]==f[ll] && ll<=k && l<=size[i]){ 
                l++; 
                ll++; 
                cn++; 
            } 
            if(cn==k) {t++;break;} 
            else j+=cn-go[cn]-1; 
        } 
        if(t) continue; 
        reverse(i); 
        for(j=1;j<=size[i];j++){ 
            l=j; 
            ll=1; 
            cn=0; 
            while(ar[i][l]==f[ll] && ll<=k && l<=size[i]){ 
                l++; 
                ll++; 
                cn++; 
            } 
            if(cn==k) {t++;break;} 
            else j+=cn-go[cn]-1; 
        } 
        reverse(i); 
        if(!t) return 0; 
    } 
    return 1; 
} 
int main() 
{ 
    int m,i,j; 
   
    scanf("%d %d",&n,&k); 
   
    for(i=1;i<=n;i++){ 
        scanf("%d",&size[i]); 
        for(j=1;j<=size[i];j++) 
            scanf("%d",&ar[i][j]); 
    } 
   
    for(i=1;i<=size[1]-k+1;i++){ 
        for(j=i;j<=i+k-1;j++){ 
            f[j-i+1]=ar[1][j]; 
        } 
        make_kmp(); 
        if(find()) {printf("YES");return 0;} 
    } 
    printf("NO"); 
    return 0; 
}

Subtask #1
2.64 / 2.64

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

Subtask #2
3.12 / 3.12

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

Subtask #3
3.6 / 3.6

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

Subtask #4
4.32 / 4.32

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

Subtask #5
4.8 / 4.8

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

Subtask #6
5.52 / 5.52

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