Submission #383628

#	Time	Username	Problem	Language	Result	Execution time	Memory
383628		rumen_m	Lottery (CEOI18_lot)	C++17	100 / 100	2021 ms	8508 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 uk1 = 1;
    int uk2 = Q;
    if(q[uk1].k<v)return ;
    int mid;
    while(uk1<uk2)
    {
        mid=  (uk1+uk2+1)>>1;
        if(q[mid].k>=v)uk1 = mid;
        else
            uk2 = mid-1;
    }
    q[uk2].p[x]++;
}
int newnum[105];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.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=Q;i>0;i--)
    {
        for(j=1;j<=n;j++)
            q[i].p[j]+=q[i+1].p[j];
    }
    for(i=1;i<=Q;i++)
        newnum[q[i].idx] = i;
    for(i=1;i<=Q;i++)
    {
        j = newnum[i];

        for(int t=1;t<=n-l+1;t++)
            cout<<q[j].p[t]<<" ";
        cout<<'\n';
    }
}

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