Submission #5881

#	Time	Username	Problem	Language	Result	Execution time	Memory
5881		baneling100	백신 (KOI13_vaccine)	C++98	24 / 24	56 ms	1488 KiB

vaccine

#include <stdio.h>

int N, K, M[101], A[101][1001], B[1001], Fail[1001];

void input(void)
{
    int i, j;

    scanf("%d %d",&N,&K);
    for(i=1 ; i<=N ; i++)
    {
        scanf("%d",&M[i]);
        for(j=1 ; j<=M[i] ; j++)
            scanf("%d",&A[i][j]);
    }
}

void makeB(int left, int right)
{
    int i;

    for(i=left ; i<=right ; i++)
        B[i-left+1]=A[1][i];
}

void makeFail(void)
{
    int i, now;

    Fail[0]=-1;
    for(i=1 ; i<=K ; i++)
    {
        now=Fail[i-1];
        while(B[now+1]!=B[i] && now>=0)
        {
            now=Fail[now];
        }
        Fail[i]=now+1;
    }
}

int compareAB(int num)
{
    int i, start=1, match=1;

    Fail[0]=0;
    while(start<=M[num]-K+1)
    {
        for(i=match ; i<=K ; i++)
        {
            if(A[num][start+i-1]!=B[i])
            {
                match=Fail[i-1]+1;
                if(i-1-Fail[i-1]==0)
                    start++;
                else
                    start+=i-1-Fail[i-1];
                break;
            }
        }
        if(i==K+1)
            return 1;
    }
    return 0;
}

void reverseA(int num)
{
    int i, temp;

    for(i=1 ; i<=M[num]/2 ; i++)
    {
        temp=A[num][i];
        A[num][i]=A[num][M[num]-i+1];
        A[num][M[num]-i+1]=temp;
    }
}

void process(void)
{
    int i, j, ok, x, y;

    for(i=1 ; i<=M[1]-K+1 ; i++)
    {
        makeB(i,i+K-1);
        makeFail();
        ok=1;
        for(j=2 ; j<=N && ok ; j++)
        {
            x=compareAB(j);
            reverseA(j);
            y=compareAB(j);
            ok=(x|y);
        }
        if(ok)
        {
            printf("YES");
            return;
        }
    }
    printf("NO");
}

int main(void)
{
    input();
    process();

    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