oj.uz

Submission #5881

# Submission time Handle Problem Language Result Execution time Memory
5881 2014-05-21T06:42:38 Z baneling100 백신 (KOI13_vaccine) C++
24 / 24
 56 ms 1488 KB 
#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

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

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

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

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

# Verdict Execution time Memory 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 56 ms 1488 KB Output is correct
5 Correct 0 ms 1488 KB Output is correct
6 Correct 4 ms 1488 KB Output is correct
7 Correct 0 ms 1488 KB Output is correct
8 Correct 8 ms 1488 KB Output is correct
9 Correct 8 ms 1488 KB Output is correct
10 Correct 8 ms 1488 KB Output is correct

Subtask #6
5.52 / 5.52

# Verdict Execution time Memory Grader output
1 Correct 0 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 8 ms 1488 KB Output is correct
5 Correct 12 ms 1488 KB Output is correct
6 Correct 16 ms 1488 KB Output is correct
7 Correct 56 ms 1488 KB Output is correct
8 Correct 12 ms 1488 KB Output is correct
9 Correct 16 ms 1488 KB Output is correct
10 Correct 12 ms 1488 KB Output is correct