#include<bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
const int MOD = 1e9 + 21;
const int MODInverse = 928571448;
int main(){
int n, l;
cin >> n >> l;
int powers[1 + n];
powers[0] = 1;
int invPowers[1 + n];
invPowers[0] = 1;
for(int i = 1; i <= n; i++){
powers[i] = (long long)powers[i - 1] * p % MOD;
invPowers[i] = (long long)invPowers[i - 1] * MODInverse % MOD;
}
vector<int> a(1 + n);
vector<long long> hashing(1 + n, 0);
for(int i = 1; i <= n; i++){
cin >> a[i];
hashing[i] = (hashing[i - 1] + powers[i] * a[i]) % MOD;
}
int q;
cin >> q;
if(n <= 300){
while(q--){
int val;
cin >> val;
vector<int> ans(1 + n, 0);
for(int i = 1; i + l - 1 <= n; i++){
for(int j = i + 1; j + l - 1 <= n; j++){
int thing = 0;
for(int k = 0; k < l; k++){
if(a[i + k] != a[j + k]){
thing++;
}
}
if(thing <= val){
ans[i]++;
ans[j]++;
}
}
}
for(int i = 1; i + l - 1 <= n; i++){
cout << ans[i] << " ";
}
cout << "\n";
}
}
else if(q == 1){
int k;
cin >> k;
if(k == 0){
map<long long, int> freq;
for(int i = 1; i + l - 1 <= n; i++){
long long num = hashing[i + l - 1] - hashing[i - 1];
num %= MOD;
num = (num * invPowers[i]) % MOD;
if(num < 0){
num += MOD;
}
freq[num]++;
}
for(int i = 1; i + l - 1 <= n; i++){
long long num = hashing[i + l - 1] - hashing[i - 1];
num %= MOD;
num = (num * invPowers[i]) % MOD;
if(num < 0){
num += MOD;
}
cout << freq[num] - 1 << " ";
}
cout << "\n";
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
3 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
32 ms |
600 KB |
Output is correct |
9 |
Correct |
24 ms |
348 KB |
Output is correct |
10 |
Correct |
15 ms |
348 KB |
Output is correct |
11 |
Correct |
14 ms |
580 KB |
Output is correct |
12 |
Correct |
20 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
3 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
32 ms |
600 KB |
Output is correct |
9 |
Correct |
24 ms |
348 KB |
Output is correct |
10 |
Correct |
15 ms |
348 KB |
Output is correct |
11 |
Correct |
14 ms |
580 KB |
Output is correct |
12 |
Correct |
20 ms |
348 KB |
Output is correct |
13 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Incorrect |
5 ms |
1116 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Incorrect |
5 ms |
1116 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
3 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
32 ms |
600 KB |
Output is correct |
9 |
Correct |
24 ms |
348 KB |
Output is correct |
10 |
Correct |
15 ms |
348 KB |
Output is correct |
11 |
Correct |
14 ms |
580 KB |
Output is correct |
12 |
Correct |
20 ms |
348 KB |
Output is correct |
13 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |