답안 #13060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13060	2015-01-28T14:05:15 Z	ejnahc	백신 (KOI13_vaccine)	C++	24 / 24	40 ms	1492 KB

vaccine

#include <cstdio>

int program[101][1001],length[1001];
int match[1001],reverse[1001],reverse_match[1001];
int N,K,L;
int pi(int *q,int *p)
{
  int i=1,j=0;
  for(;i<=K;)
  {
    if(!j||p[i]==p[j])
    {
      j++;i++;q[i]=j;
    }
    else j=q[j];
  }
}
int kmp(int *q,int *a,int *p,int len)
{
  int i,j;
  for(i=j=1;i<=len;)
  {
    if(!j||a[i]==p[j]){i++;j++;}
    else j=q[j];
    if(j==K+1) return 1;
  }
  return 0;
}
int main()
{
  int i,j,k,t,q,s;
  
  scanf("%d%d",&N,&K);
  for(i=0;i<N;i++)
  {
    scanf("%d",&length[i]);
    for(j=1;j<=length[i];scanf("%d",&program[i][j++]));
  }
  for(i=1;program[0][i+K];i++)
  {
    pi(match,&program[0][i-1]);
    for(j=1;j<=K;j++)
    {
      reverse[j]=program[0][i+K-j];
    }
    pi(reverse_match,reverse);
    for(s=j=1;j<N;j++)
    {
      if(kmp(match,program[j],&program[0][i-1],length[j]))s++;
      else if(kmp(reverse_match,program[j],reverse,length[j]))s++;
      else break;
    }
    if(s==N){puts("YES");return 0;}
  }
  puts("NO");
}

Subtask #1

2.64 / 2.64

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

Subtask #2

3.12 / 3.12

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

Subtask #3

3.6 / 3.6

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

Subtask #4

4.32 / 4.32

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

Subtask #5

4.8 / 4.8

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

Subtask #6

5.52 / 5.52

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