Submission #599064

#	Time	Username	Problem	Language	Result	Execution time	Memory
599064		isaachew	Lottery (CEOI18_lot)	C++17	100 / 100	993 ms	12740 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<int> queries;
    std::vector<int> s_indices;
    std::vector<int> qlt;
    int q;
    std::cin>>q;
    for(int j=q;j--;){
        int k;
        std::cin>>k;
        queries.push_back(k);
        s_indices.push_back(j);
    }
    s_indices.push_back(q);
    queries.push_back(l+1);
    
    std::sort(s_indices.begin(),s_indices.end(),[queries](int a,int b){return queries[a]<queries[b];});
    int nqs=0;
    for(int i=0;i<=l;i++){
        while(i>queries[s_indices[nqs]]){
            nqs++;
        }
        qlt.push_back(nqs);
        //std::cout<<nqs<<'\n';
    }
    
    std::vector<std::vector<int>> diffcnt(n-l+1,std::vector<int>(q+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][qlt[sumd]]++;
                diffcnt[i+d][qlt[sumd]]++;
            }
        }
    }
    std::vector<std::vector<int>> tdiffs(n-l+1,std::vector<int>(q+1));
    for(int i=0;i<n-l+1;i++){
        int cur=0;
        for(int j=0;j<=q;j++){
            cur+=diffcnt[i][j];
            tdiffs[i][j]=cur;
        }
    }
    for(int i=0;i<q;i++){
        int ind=0;
        while(s_indices[ind]!=i)ind++;//linear search; doesn't matter
        for(int j=0;j<n-l+1;j++){
            std::cout<<tdiffs[j][ind]<<' ';
        }
        std::cout<<'\n';
    }
    
}

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