Submission #966919

#TimeUsernameProblemLanguageResultExecution timeMemory
966919Charizard2021Lottery (CEOI18_lot)C++17
65 / 100
1304 ms16468 KiB
#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 <= 2000){ vector<vector<int> > ans(1 + n, vector<int>(1 + n, 0)); for(int i = 1; i + l - 1 <= n; i++){ for(int j = i + 1; j + l - 1 <= n; j++){ for(int k = 0; k < l; k++){ if(a[i + k] != a[j + k]){ ans[i][j]++; ans[j][i]++; } } } } while(q--){ int val; cin >> val; for(int i = 1; i + l - 1 <= n; i++){ int ans2 =0 ; for(int j = 1; j + l - 1 <= n; j++){ if(i != j){ if(ans[i][j] <= val){ ans2++; } } } cout << ans2 << " "; } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...