Submission #897830

#	Time	Username	Problem	Language	Result	Execution time	Memory
897830		alexdd	Lottery (CEOI18_lot)	C++17	80 / 100	3102 ms	4072 KiB

lot

#include<bits/stdc++.h>
using namespace std;
int n,lun,cntq;
int a[10005];
int cntd[10005];
vector<int> qrys;
int rez[105][10005];
void solve()
{
    for(int dif=-n;dif<=n;dif++)
    {
        if(dif==0)
            continue;
        for(int i=1;i<=n;i++)
        {
            cntd[i] = cntd[i-1];
            if(i+dif>0 && i+dif<=n && a[i]!=a[i+dif])
                cntd[i]++;
        }
        for(int i=max(1,-dif+1);i<=min(n-lun+1,n-dif-lun+1);i++)
        {
            int aux = 0;
            aux = cntd[i+lun-1] - cntd[i-1];
            for(int j=0;j<cntq;j++)
            {
                if(aux <= qrys[j])
                    rez[j][i]++;
            }
        }
    }
}
signed main()
{
    cin>>n>>lun;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cin>>cntq;
    qrys.resize(cntq);
    for(int i=0;i<cntq;i++)
    {
        cin>>qrys[i];
    }
    solve();
    for(int i=0;i<cntq;i++)
    {
        for(int j=1;j+lun-1<=n;j++)
            cout<<rez[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}
/**

cntd[dif][poz] = numarul de mismatches a[x] != a[x+dif], unde x = 1..poz
cntc[dif][i] = cntd[dif][i+lun-1] - cntd[dif][i-1] = distanta de la intervalul i..i+lun-1 la i+dif..i+dif+lun-1 este

distanta de la intervalul i..i+lun-1 la i+dif..i+dif+lun-1 este:
cntd[dif][i+lun-1] - cntd[dif][i-1]

ne fixam dif
vedem cum influenteaza dif cele q queryuri

*/

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