# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
920065 | Jawad_Akbar_JJ | Lottery (CEOI18_lot) | C++17 | 128 ms | 740 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
using namespace std;
const int N = 10000 + 10;
long long mod[2];
int hsh[N][2];
int a[N];
int dp[N][2];
int d[2];
int ans[N];
int res[N][2];
void calc(int t,int i){
hsh[i][t] = (1LL * hsh[i-1][t] * d[t] + a[i]) % mod[t];
}
int get(int t,int l,int r){
int H = 1LL * hsh[l][t] * dp[r - l][t] % mod[t];
return (hsh[r][t] - H + mod[t]) % mod[t];
}
signed main(){
mod[0] = 1e9 + 7;
mod[1] = 998244353;
d[0] = 256;
d[1] = 149;
dp[0][0] = dp[0][1] = 1;
for (int i=1;i<N;i++)
dp[i][0] = 1LL * dp[i-1][0] * d[0] % mod[0];
for (int i=1;i<N;i++)
dp[i][1] = 1LL * dp[i-1][1] * d[1] % mod[1];
int n,l;
scanf("%d%d",&n,&l);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=n;i++){
calc(0,i);
calc(1,i);
}
for (int i=0;i + l <= n;i++)
res[i][0] = get(0,i,i+l);
for (int i=0;i + l <= n;i++)
res[i][1] = get(1,i,i+l);
for (int i=0;i + l <= n;i++){
for (int j=0;j + l <= n;j++)
if (res[i][0] == res[j][0] and res[i][1] == res[j][1])
ans[i+1]++;
}
int q;
scanf("%d",&q);
scanf("%d",&q);
for (int i=0;i+l <=n;i++)
printf("%d ",ans[i+1]-1);
printf("\n");
}
Compilation message (stderr)
# | 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... |