Submission #4945

#	Time	Username	Problem	Language	Result	Execution time	Memory
4945		hana5505	백신 (KOI13_vaccine)	C++98	24 / 24	48 ms	1488 KiB

vaccine

#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
• Subtask 2: 3.12 / 3.12
• Subtask 3: 3.6 / 3.6
• Subtask 4: 4.32 / 4.32
• Subtask 5: 4.8 / 4.8
• Subtask 6: 5.52 / 5.52