Cod sursa(job #1161972)

Utilizator Vladinho97Iordan Vlad Vladinho97 Data 31 martie 2014 15:59:41
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <vector>
using namespace std;
int arb[66000],v[30009],ans[30009];
void init(int inc,int sf,int poz)
{
    if(inc==sf)
    {
        arb[poz]=1;
        return;
    }
    arb[poz]=sf-inc+1;
    int med=(inc+sf)/2;
    init(inc,med,poz*2);
    init(med+1,sf,poz*2+1);
}
void update(int inc,int sf,int x,int poz)
{
    arb[poz]--;
    if(inc==sf)
        return;
    int med=(inc+sf)/2;
    if(x>med)
        update(med+1,sf,x,poz*2+1);
    else
        update(inc,med,x,poz*2);
}
int find(int inc,int sf,int x,int poz)
{
    int med=(inc+sf)/2;
    if(inc==sf)
        return inc;
    if(arb[2*poz]>=x)
        return find(inc,med,x,poz*2);
    return find(med+1,sf,x-arb[2*poz],poz*2+1);
}
int main()
{
    int n,i,x;
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    init(1,n,1);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    for(i=n;i>=1;i--)
    {
        x=find(1,n,v[i],1);
        update(1,n,x,1);
        ans[x]=i;
    }
    for(i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}