This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |