Submission #966915

#	Time	Username	Problem	Language	Result	Execution time	Memory
966915		Charizard2021	Lottery (CEOI18_lot)	C++17	0 / 100	5 ms	1116 KiB

lot

#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(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";
        }
    }
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20