oj.uz

Submission #13060

# Submission time Handle Problem Language Result Execution time Memory
13060 2015-01-28T14:05:15 Z ejnahc 백신 (KOI13_vaccine) C++
24 / 24
 40 ms 1492 KB 
#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

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

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

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

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

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

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