Submission #383624

#	Time	Username	Problem	Language	Result	Execution time	Memory
383624		rumen_m	Lottery (CEOI18_lot)	C++17	80 / 100	3092 ms	4460 KiB

lot

# include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
int a[maxn];
int calc(int x, int y, int l)
{
    int sum = 0;
    int i;
    for(i=0;i<l;i++)
    {
        if(a[x+i]!=a[y+i])sum++;
    }
    return sum;
}
struct queries
{
    int idx;
    int p[maxn];
    int k;
};
queries q[105];
bool cmp(queries i, queries j)
{
    return i.k>j.k;
}int Q;
void add(int x, int v)
{
    int i;
    for(i=1;i<=Q;i++)
    {
        if(q[i].k<v)return ;
        q[i].p[x]++;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,l;
    cin>>n>>l;
    int i,j;
    for(i=1;i<=n;i++)cin>>a[i];

    cin>>Q;
    for(i=1;i<=Q;i++){q[i].idx=i;cin>>q[i].k;}
    sort(q+1,q+Q+1,cmp);
    for(i=2;i<=n-l+1;i++)
    {
        int num = calc(1,i,l);
        add(1,num);
        add(i,num);
        int f = 1;
        int s = i;
     //   cout<<f<<" - "<<s<<" : "<<num<<endl;
        for(j=i+1;j<=n-l+1;j++)
        {
            if(a[f]!=a[s])num--;
            f++;
            s++;
            if(a[f+l-1]!=a[s+l-1])num++;
            add(f,num);
            add(s,num);
           // cout<<f<<" - "<<s<<" : "<<num<<endl;
        }
    }
    for(i=1;i<=Q;i++)
    {
        j = 1;
        while(q[j].idx!=i)j++;
        for(int t=1;t<=n-l+1;t++)
            cout<<q[j].p[t]<<" ";
        cout<<endl;
    }
}

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