oj.uz

Submission #260530

# Submission time Handle Problem Language Result Execution time Memory
260530 2020-08-10T13:19:03 Z stefantaga Lottery (CEOI18_lot) C++14
0 / 100
 4 ms 1408 KB 
#include <bits/stdc++.h>

using namespace std;
int n,l,i,v[10005],nr,q,smen[105][10005],solutie[105][10005],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]++;
            smen[j][sol]++;
        }
    }
    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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 896 KB Output isn't correct
3 Halted 0 ms 0 KB -