Submission #1094001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094001		alexander707070	Lottery (CEOI18_lot)	C++17	100 / 100	569 ms	8532 KiB

lot

#include<bits/stdc++.h>
#define MAXN 10007
using namespace std;

int n,l,q;
int a[MAXN];
pair<int,int> k[MAXN];

int br[MAXN][107],matches,to[MAXN],ans[MAXN],pos[MAXN];

int calc(int x,int y){
    int res=0;
    for(int i=0;i<l;i++){
        if(a[x+i]==a[y+i])res++;
    }
    return res;
}

int main(){

    cin>>n>>l;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>k[i].first;
        k[i].first=l-k[i].first;

        k[i].second=i;
    }

    sort(k+1,k+q+1);

    for(int i=1;i<=q;i++){
        pos[k[i].second]=i;
    }

    int pt=0;
    for(int i=0;i<=l;i++){
        while(pt<q and k[pt+1].first<=i)pt++;
        to[i]=pt;
    }

    for(int dist=1;dist<=n;dist++){

        for(int i=1;i+dist+l-1<=n;i++){
            if(i==1)matches=calc(i,i+dist);
            else{
                if(a[i-1]==a[i+dist-1])matches--;
                if(a[i+l-1]==a[i+dist+l-1])matches++;
            }
            br[i][to[matches]]++;
            br[i+dist][to[matches]]++;
        }
    }

    for(int i=1;i<=n;i++){
        for(int f=q-1;f>=1;f--){
            br[i][f]+=br[i][f+1];
        }
    }

    for(int i=1;i<=q;i++){
        for(int f=1;f+l-1<=n;f++){
            cout<<br[f][pos[i]]<<" ";
        }
        cout<<"\n";
    }

    return 0;
}

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