Submission #13060

#	Time	Username	Problem	Language	Result	Execution time	Memory
13060		ejnahc	백신 (KOI13_vaccine)	C++98	24 / 24	40 ms	1492 KiB

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
• 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