Submission #966922

#	Time	Username	Problem	Language	Result	Execution time	Memory
966922		Charizard2021	Lottery (CEOI18_lot)	C++17	65 / 100	1308 ms	65536 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;
    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";
        }
        else{
            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";
            }
        }
    }
}

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