Cod sursa(job #1051364)

Utilizator heracleRadu Muntean heracle Data 9 decembrie 2013 22:50:57
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>

const int Q=30002;
int val[Q],rez[Q], arb[1<<18];;
int x;
int make_arb(int val,int st, int dr)
{
    if(st==dr)
    {
        arb[val]=1;
        return 1;
    }
    else
    {
        x= make_arb(val*2,st, (st+dr)/2)+make_arb(val*2+1, (st+dr)/2+1,dr);
        arb[val]=x;
        return x;
    }

}

int loc;

int find_loc(int val, int st, int dr)
{
    int rez;
    if(st==dr)
    {
        if(arb[val]==0)
            return -1;
        if(loc>1)
        {
            loc--;
            return -1;
        }
        arb[val]=0;
        return st;
    }



    if(arb[val]<loc)
    {
        loc-=arb[val];
        return -1;
        //rez=find_loc(val+1,loc,(st+dr)/2+1,dr);
        //arb[val]--;
    }
    else
    {
        rez=find_loc(val*2,st,(st+dr)/2);
        if(rez!=-1)
            arb[val]--;
    }

    if(rez==-1)
    {
        rez=find_loc(val*2+1,(st+dr)/2+1,dr);
        arb[val]--;
    }

    return rez;
}

int n,h;

int solve(int locact)
{
    int act;
    loc=locact;
    act=find_loc(1,1,n);
    return act;

}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);


    scanf("%d",&n);

    for(int i=1; i<=n; i++)
        scanf("%d",&val[n-i+1]);

    make_arb(1,1,n);
    int g;
    for(int i=1; i<=n; i++)
    {
        g=solve(val[i]);
        rez[g]=n-i+1;
    }

    for(int i=1; i<=n; i++)
        printf("%d\n",rez[i]);
    return 0;
}