oj.uz

Submission #966915

# Submission time Handle Problem Language Result Execution time Memory
966915 2024-04-20T15:31:55 Z Charizard2021 Lottery (CEOI18_lot) C++17
0 / 100
 5 ms 1116 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Incorrect 5 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Incorrect 5 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -