oj.uz

Submission #1128

# Submission time Handle Problem Language Result Execution time Memory
1128 2013-06-26T08:16:21 Z tncks0121 백신 (KOI13_vaccine) C++
24 / 24
 373 ms 39992 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, k;
int m[1000];
int str[1000][10000];
int failure[10000];
bool ans;
void input ()
{
FILE* fp = stdin;
fscanf (fp, "%d%d", &n, &k); n*=10;
for (int i=0; i<n; i+=10) {
fscanf (fp, "%d", &m[i]);
for (int j=0; j<m[i]; j++)
fscanf (fp, "%d", &str[i][j]);
  for(int k=i+1; k<i+10; k++) {
    m[k]=m[i];
    for(int j=0; j<m[k]; j++) str[k][j] = str[i][j];
  }
}
}
void reverse (int m, int* arr)
{
for (int i=0; i<m/2; i++)
swap(arr[i], arr[m-i-1]);
}
// kmp algorithm
void get_failure_func (int* arr)
{
int j=-1;
failure[0] = -1;
for (int i=1; i<k; i++) {
while (j>=0 && arr[j+1] != arr[i])
j = failure[j];
if (arr[j+1] == arr[i]) j++;
failure[i] = j;
}
}
// kmp algorithm
bool find_string (int* p1, int m, int* p2)
{
int j=-1;
for (int i=0; i<m; i++) {
while (j>=0 && p2[j+1] != p1[i])
j = failure[j];
if (p2[j+1] == p1[i]) j++;
if (j == k-1)
return true;
}return false;
}
bool check_answer (int* p)
{
for (int i=1; i<n; i++) {
if (!find_string (str[i], m[i], p)) {
reverse (m[i], str[i]);
if (!find_string (str[i], m[i], p))
return false;
}
}
return true;
}
bool solve ()
{
if (m[0] < k) return false;
for (int i=0; i<=m[0]-k; i++) {
get_failure_func (str[0] + i);
if (check_answer (str[0] + i))
return true;
}
reverse (m[0], str[0]);
for (int i=0; i<=m[0]-k; i++) {
get_failure_func (str[0] + i);
if (check_answer (str[0] + i))
return true;
}
return false;
}
void output ()
{
FILE* fp = stdout;
if (ans) fprintf (fp, "YES\n");
else fprintf (fp, "NO\n");
}
int main()
{
input ();
ans = solve ();
output ();
return 0;
}

Subtask #1
2.64 / 2.64

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39992 KB Output is correct
2 Correct 0 ms 39992 KB Output is correct
3 Correct 0 ms 39992 KB Output is correct
4 Correct 0 ms 39992 KB Output is correct
5 Correct 0 ms 39992 KB Output is correct
6 Correct 0 ms 39992 KB Output is correct
7 Correct 0 ms 39992 KB Output is correct
8 Correct 0 ms 39992 KB Output is correct
9 Correct 0 ms 39992 KB Output is correct
10 Correct 0 ms 39992 KB Output is correct

Subtask #2
3.12 / 3.12

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39992 KB Output is correct
2 Correct 0 ms 39992 KB Output is correct
3 Correct 0 ms 39992 KB Output is correct
4 Correct 0 ms 39992 KB Output is correct
5 Correct 0 ms 39992 KB Output is correct
6 Correct 0 ms 39992 KB Output is correct
7 Correct 0 ms 39992 KB Output is correct
8 Correct 0 ms 39992 KB Output is correct
9 Correct 0 ms 39992 KB Output is correct
10 Correct 0 ms 39992 KB Output is correct

Subtask #3
3.6 / 3.6

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39992 KB Output is correct
2 Correct 0 ms 39992 KB Output is correct
3 Correct 0 ms 39992 KB Output is correct
4 Correct 0 ms 39992 KB Output is correct
5 Correct 0 ms 39992 KB Output is correct
6 Correct 0 ms 39992 KB Output is correct
7 Correct 0 ms 39992 KB Output is correct
8 Correct 0 ms 39992 KB Output is correct
9 Correct 1 ms 39992 KB Output is correct
10 Correct 0 ms 39992 KB Output is correct

Subtask #4
4.32 / 4.32

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39992 KB Output is correct
2 Correct 1 ms 39992 KB Output is correct
3 Correct 0 ms 39992 KB Output is correct
4 Correct 0 ms 39992 KB Output is correct
5 Correct 1 ms 39992 KB Output is correct
6 Correct 1 ms 39992 KB Output is correct
7 Correct 1 ms 39992 KB Output is correct
8 Correct 0 ms 39992 KB Output is correct
9 Correct 2 ms 39992 KB Output is correct
10 Correct 1 ms 39992 KB Output is correct

Subtask #5
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 3 ms 39992 KB Output is correct
2 Correct 5 ms 39992 KB Output is correct
3 Correct 4 ms 39992 KB Output is correct
4 Correct 369 ms 39992 KB Output is correct
5 Correct 2 ms 39992 KB Output is correct
6 Correct 6 ms 39992 KB Output is correct
7 Correct 6 ms 39992 KB Output is correct
8 Correct 12 ms 39992 KB Output is correct
9 Correct 14 ms 39992 KB Output is correct
10 Correct 35 ms 39992 KB Output is correct

Subtask #6
5.52 / 5.52

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39992 KB Output is correct
2 Correct 20 ms 39992 KB Output is correct
3 Correct 23 ms 39992 KB Output is correct
4 Correct 11 ms 39992 KB Output is correct
5 Correct 23 ms 39992 KB Output is correct
6 Correct 30 ms 39992 KB Output is correct
7 Correct 373 ms 39992 KB Output is correct
8 Correct 14 ms 39992 KB Output is correct
9 Correct 49 ms 39992 KB Output is correct
10 Correct 46 ms 39992 KB Output is correct