Submission #260534

#	Time	Username	Problem	Language	Result	Execution time	Memory
260534		stefantaga	Lottery (CEOI18_lot)	C++14	45 / 100	3081 ms	8696 KiB

lot

#include <bits/stdc++.h>

using namespace std;
int n,l,i,v[10005],nr,q,smen[10005][105],solutie[10005][105],j,numar,k,st,dr,mij,sol;
struct wow
{
    int poz,val;
}query[105];
map <int,int> m;
bool compare (wow a,wow b)
{
    return a.val<b.val;
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>l;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
        m[v[i]]=1;
    }
    cin>>q;
    for (i=1;i<=q;i++)
    {
        cin>>query[i].val;
        query[i].poz=i;
    }
    sort (query+1,query+q+1,compare);
    nr=0;
    for (auto ind : m)
    {
        nr++;
        m[ind.first]=nr;
    }
    for (i=1;i<=n;i++)
    {
        v[i]=m[v[i]];
    }
    for (i=1;i<=n-l+1;i++)
    {
        for (j=i+1;j<=n-l+1;j++)
        {
            numar=0;
            for (k=1;k<=l;k++)
            {
                if (v[i+k-1]!=v[j+k-1])
                {
                    numar++;
                }
            }
            st=1;
            dr=q;
            sol=0;
            while (st<=dr)
            {
                mij=(st+dr)/2;
                if (query[mij].val<numar)
                {
                    sol=mij;
                    st=mij+1;
                }
                else
                {
                    dr=mij-1;
                }
            }
            smen[i][sol+1]++;
            smen[j][sol+1]++;
        }
    }
    for (i=1;i<=n-l+1;i++)
    {
        for (j=1;j<=q;j++)
        {
            smen[i][j]+=smen[i][j-1];
            solutie[i][query[j].poz]+=smen[i][j];
        }
    }
    for (j=1;j<=q;j++)
    {
        for (i=1;i<=n-l+1;i++)
        {
            cout<<solutie[i][j]<<" ";
        }
        cout<<'\n';
    }
    return 0;
}

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