Cod sursa(job #1490580)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 23 septembrie 2015 20:14:13
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<cstdio>
int v[30005],po[30005],ai[90005],an[30005];
void update(int nod,int x,int st,int dr)
{
    ai[nod]++;
    if(dr==x)
    {
        return ;
    }
    int mi;
    mi=(st+dr)/2;
    if(x<=mi)
    update(nod*2,x,st,mi);
    else
    {
        update(nod*2+1,x,mi+1,dr);
    }
}
int cueri(int nod,int x,int st,int dr)
{
    if(st==dr || dr==x)
    return ai[nod];
    int mi;
    mi=(st+dr)/2;
    if(x<=mi)
    return cueri(nod*2,x,st,mi);
    else
    return ai[nod*2]+cueri(nod*2+1,x,mi+1,dr);
}
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int n,i,j,st,dr,mi,la,x;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&v[i]);
    for(i=n;i>=1;i--)
    {
        st=v[i];dr=n;
        while(st<=dr)
        {
            mi=(st+dr)/2;
            x=cueri(1,mi,1,n);
            if(v[i]+x<=mi)
            {
                dr=mi-1;
                la=mi;
            }
            else
            {
                st=mi+1;
            }
        }
        po[i]=la;
        update(1,la,1,n);
    }
    for(i=1;i<=n;i++)
    an[po[i]]=i;
    for(i=1;i<=n;i++)
    printf("%d\n",an[i]);
    return 0;
}