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<bits/stdc++.h>
using namespace std;
bitset<2500>ext;
typedef long long ll;
ll p1=10061,p2=100000007,n1=396,n2=117;
ll PW(ll X,ll Y,ll P)
{
ll I=1ll<<62,cs=1;
for(;I;I>>=1)
{
cs=cs*cs%P;
if(I&Y)cs=cs*X%P;
}
return cs;
}
int N,K;
ll PS1,PS2;
vector<int>V;
struct C{
ll H1,H2;
int from;
C RG(C&X)
{
return {((H1-X.H1*PS1)%p1+p1)%p1,((H2-X.H2*PS2)%p2+p2)%p2};
}
bool operator<(const C&X)const{return H1==X.H1?H2<X.H2:H1<X.H1;}
bool operator==(const C&X)const{return H1==X.H1&&H2==X.H2;}
};
vector<C>VC,TV,TTV;
void BH(int n)
{
int i;
TV.resize(n+1);
TV[0]={0,0,0};
for(i=0;i<n;i++)
TV[i+1]={(TV[i].H1*n1+V[i])%p1,(TV[i].H2*n2+V[i])%p2};
}
int in()
{
int M;
cin>>M;
V.resize(M);
for(int&I:V)cin>>I;
return M;
}
void getH()
{
TTV.clear();
for(int i=K;i<TV.size();i++)
{
TTV.push_back(TV[i].RG(TV[i-K]));
}
}
void first()
{
VC.clear();
int L=in();
BH(L);
getH();
VC.insert(VC.end(),TTV.begin(),TTV.end());
sort(VC.begin(),VC.end());
VC.resize(distance(VC.begin(),unique(VC.begin(),VC.end())) );
for(auto&I:VC)I.from=(&I-&VC[0]);
}
void second()
{
ext.reset();
int L=in();
BH(L);
getH();
for(auto&I:TTV)
{
if(lower_bound(VC.begin(),VC.end(),I)!=VC.end()&&I==*lower_bound(VC.begin(),VC.end(),I))
ext.set((*lower_bound(VC.begin(),VC.end(),I)).from);
}
reverse(V.begin(), V.end());
BH(L);
getH();
for(auto&I:TTV)
{
if(lower_bound(VC.begin(),VC.end(),I)!=VC.end()&&I==*lower_bound(VC.begin(),VC.end(),I))
ext.set((*lower_bound(VC.begin(),VC.end(),I)).from);
}
int w=0;
for(int i=0;i<VC.size();i++)
{
if(ext[VC[i].from])
VC[w++]=VC[i];
}
VC.resize(w);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>N>>K;
PS1=PW(n1,K,p1),PS2=PW(n2,K,p2);
first();
int i;
for(i=1;i<N&&!VC.empty();i++)
second();
printf("%s",VC.empty()? "NO":"YES");
}
Compilation message (stderr)
vaccine.cpp: In function 'void getH()':
vaccine.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=K;i<TV.size();i++)
~^~~~~~~~~~
vaccine.cpp: In function 'void second()':
vaccine.cpp:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<VC.size();i++)
~^~~~~~~~~~
# | 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... |