Cod sursa(job #1047531)

Utilizator heracleRadu Muntean heracle Data 4 decembrie 2013 17:20:45
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>

/*
int max(int a, int b)
{
    return a>b ? a : b;
}

int make_arb(int val,int st, int dr)
{
    if(st!=dr)
    {
        arb[val]=max( make_arb(2*val,st,(dr+st)/2), make_arb(2*val+1,(st+dr)/2+1,dr));
    }
    else
    {
        pozarb[st]=val;
        arb[val]=v[st];
    }
    return arb[val];
}

void modif_arb(int poz)
{
    arb[poz]=max(arb[2*poz],arb[2*poz+1]);
    if(poz/2!=0)
        modif_arb(poz/2);
}

int find_max(int poz,int s, int d,int st,int dr)
{
    if(s>=st && d<=dr)
        return arb[poz];
    if(st>d || dr<s)
        return 0;

    return max(find_max(poz*2,s,(s+d)/2,st,dr),find_max(poz*2+1,(s+d)/2+1,d,st,dr));


}

*/
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 find_loc(int val,int loc, int st, int dr)
{
    int rez;
    if(arb[val]==1)
    {
        arb[val]=0;
        return val;
    }

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

int n,h;

int solve(int loc)
{
    int act;
    act=find_loc(1,loc,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);

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

    return 0;
}