oj.uz

Submission #14192

# Submission time Handle Problem Language Result Execution time Memory
14192 2015-05-03T12:35:50 Z paulsohn 백신 (KOI13_vaccine) C++
24 / 24
 41 ms 5192 KB 
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
int N,K;
vector<int> code[100], T[2000], cpy;
 
void mkt(int* p, int o){
    int i=1,j=0;
    T[o].push_back(-1);
    while(i<K){
        if(p[i]==p[j]){
            T[o].push_back(j);
            ++i; ++j;
        }
        else if(j>0) j=T[o][j];
        else{
            T[o].push_back(0);
            ++i;
        }
    }
}
 
bool KMP(int r, int m){
    int i=0,j=0,s=0;
    while(i+j<code[r].size()){
        if(code[r][i+j]==code[0][m+j]){
            ++j;
            ++s;
        }
        else if(j){
            i+=j-T[m<<1][j];
            j=T[m<<1][j];
        }
        else ++i;
        if(j==K) return true;
    }
    i=0,j=0;
    while(i+j<code[r].size()){
        if(code[r][i+j]==code[0][m+K-1-j]){
            ++j;
        }
        else if(j){
            i+=j-T[(m<<1)+1][j];
            j=T[(m<<1)+1][j];
        }
        else ++i;
        if(j==K) return true;
    }
    return false;
}
 
int main(){
    int i,j,m,w,*p;
    scanf("%d%d",&N,&K);
    for(i=0;i<N;++i){
        scanf("%d",&m);
        for(j=0;j<m;++j){
            scanf("%d",&w);
            code[i].push_back(w);
        }
    }
    for(j=0;j<=code[0].size()-K;++j){
        cpy=code[0];
        p=&(cpy[j]);
        mkt(p,j<<1);
        reverse(p,p+K);
        mkt(p,(j<<1)+1);
    }
 
    for(j=0;j<=code[0].size()-K;++j){
        for(i=1;i<N;++i){
            if(!KMP(i,j)) break;
        }
        if(i==N){ printf("YES"); return 0; }
    }
    printf("NO"); return 0;
    return 0;
}

Subtask #1
2.64 / 2.64

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

Subtask #2
3.12 / 3.12

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

Subtask #3
3.6 / 3.6

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

Subtask #4
4.32 / 4.32

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

Subtask #5
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1892 KB Output is correct
2 Correct 7 ms 2156 KB Output is correct
3 Correct 8 ms 2024 KB Output is correct
4 Correct 35 ms 4404 KB Output is correct
5 Correct 0 ms 1892 KB Output is correct
6 Correct 7 ms 2024 KB Output is correct
7 Correct 8 ms 2156 KB Output is correct
8 Correct 6 ms 3344 KB Output is correct
9 Correct 23 ms 3608 KB Output is correct
10 Correct 15 ms 3080 KB Output is correct

Subtask #6
5.52 / 5.52

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2948 KB Output is correct
2 Correct 13 ms 3452 KB Output is correct
3 Correct 11 ms 5192 KB Output is correct
4 Correct 11 ms 2948 KB Output is correct
5 Correct 22 ms 3212 KB Output is correct
6 Correct 41 ms 5060 KB Output is correct
7 Correct 29 ms 5192 KB Output is correct
8 Correct 13 ms 3344 KB Output is correct
9 Correct 31 ms 4268 KB Output is correct
10 Correct 17 ms 4136 KB Output is correct