Submission #599041

#	Time	Username	Problem	Language	Result	Execution time	Memory
599041		isaachew	Lottery (CEOI18_lot)	C++17	45 / 100	789 ms	65536 KiB

lot

#include <bits/stdc++.h>
/*
 Hamming distance
 
 High time limit - O(n^2)? O(n sqrt n Q)?
 
 ST1: O(nlq)?
 ST3: find exact matches in O(N log N)
 
 Find number of strings with Hamming distance <= k
 
 O(n^2l)
 Precompute everything
 Speed up finding differences
 
 Differences can be found in O(n^2) by marking which numbers are the same as the number x away
 
 Differences between x and x+n found
 
 k<=l
 */
int n,l;
int main(){
    std::cin>>n>>l;
    std::vector<int> a;
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        a.push_back(x);
    }
    std::vector<std::vector<int>> diffcnt(n-l+1,std::vector<int>(l+1));
    for(int d=1;d<=n-l;d++){
        std::vector<bool> diff_ds;
        for(int i=0;i<n-d;i++){
            diff_ds.push_back(a[i]!=a[i+d]);
        }
        int sumd=0;
        for(int i=-l+1;i<n-l+1;i++){
            if(i<=n-l){
                sumd+=diff_ds[i+l-1];
            }
            if(i>0){
                sumd-=diff_ds[i-1];
            }
            if(i>=0&&i<(n-l+1)-d){
                //std::cout<<i<<' '<<i+d<<' '<<sumd<<'\n';
                diffcnt[i][sumd]++;
                diffcnt[i+d][sumd]++;
            }
        }
    }
    std::vector<std::vector<int>> tdiffs(n-l+1,std::vector<int>(l+1));
    for(int i=0;i<n-l+1;i++){
        int cur=0;
        for(int j=0;j<=l;j++){
            cur+=diffcnt[i][j];
            tdiffs[i][j]=cur;
        }
    }
    int q;
    std::cin>>q;
    for(;q--;){
        int k;
        std::cin>>k;
        for(int i=0;i<n-l+1;i++){
            std::cout<<tdiffs[i][k]<<' ';
        }
        std::cout<<'\n';
    }
}

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