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 <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int N=1e4+1;
int a[N],l,n,cpy[N];
bool posa=0;
map<int,int> ans[N];
vector<vector<int>> hp;
void level_up()
{
if(posa)
return;
for(int i=0;i<(n-l+1);i++)
{
for(int j=i+1;j<(n-l+1);j++)
{
int c=0;
for(int dl=0;dl<l;dl++)
{
c+=(hp[i][dl]!=hp[j][dl]);
}
ans[i][c]++;
ans[j][c]++;
}
}
posa=1;
}
int main()
{
cin>>n>>l;
for(int i=0;i<n;i++)
{
cin>>a[i];
cpy[i]=a[i];
}
int q;
cin>>q;
if(q==1)
{
int k;
cin>>k;
if(k==0)
{
// sort(cpy,cpy+n);
// for(int i=0;i<n;i++)
// a[i]=lower_bound(cpy,cpy+n,a[i])-cpy;
map<long long,int> cnt;
for(int i=0;(i+l-1)<n;i++)
{
long long hash=0,base=717,mod=1e9+9;
for(int j=0;j<l;j++)
{
hash=(hash*base)%mod;
hash+=a[j+i];
hash%=mod;
}
cnt[hash]++;
}
for(int i=0;(i+l-1)<n;i++)
{
long long hash=0,base=717,mod=1e9+9;
for(int j=0;j<l;j++)
{
hash=(hash*base)%mod;
hash+=a[j+i];
hash%=mod;
}
cout<<cnt[hash]-1<<' ';
}
cout<<'\n';
}
else
{
vector<int> ans(n);
for(int i=0;(i+l-1)<n;i++)
{
for(int j=i+1;(j+l-1)<n;j++)
{
int dif=0;
bool pos=1;
for(int lp=0;lp<l;lp++)
{
if((l-lp+dif)<=k)
break;
dif+=(a[i+lp]!=a[j+lp]);
if(dif>k)
{
pos=0;
break;
}
}
ans[i]+=pos;
ans[j]+=pos;
}
}
for(int i=0;(i+l-1)<n;i++)
cout<<ans[i]<<' ';
cout<<endl;
}
}
else
{
for(int i=0;(i+l-1)<n;i++)
{
vector<int> ap;
for(int j=0;j<l;j++)
ap.push_back(a[i+j]);
hp.push_back(ap);
}
level_up();
while(q--)
{
int k;
cin>>k;
for(int i=0;(i+l-1)<n;i++)
{
int sp=0;
for(int lp=0;lp<=k;lp++)
if(ans[i].find(lp)!=ans[i].end())
sp+=ans[i][lp];
cout<<sp<<' ';
}
cout<<'\n';
}
}
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... |