이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
long long powers[1 + n];
powers[0] = 1;
long long invPowers[1 + n];
invPowers[0] = 1;
for(int i = 1; i <= n; i++){
powers[i] = powers[i - 1] * p % MOD;
invPowers[i] = 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;
if(num < 0){
num += MOD;
}
num = (num * invPowers[i]) % MOD;
freq[num]++;
}
for(int i = 1; i + l - 1 <= n; i++){
long long num = hashing[i + l - 1] - hashing[i - 1];
num %= MOD;
if(num < 0){
num += MOD;
}
num = (num * invPowers[i]) % MOD;
cout << freq[num] - 1 << " ";
}
cout << "\n";
}
}
}
# | 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... |