Cod sursa(job #1408647)

Utilizator gabib97Gabriel Boroghina gabib97 Data 30 martie 2015 10:05:04
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>

using namespace std;
int n,i,a[30001],sol[30001],h[66005],poz[30001],x;
void creare(int p,int x,int y)
{
    if (x==y) h[p]=1,poz[x]=p;
    else
    {
        int m=(x+y)>>1;
        creare(2*p,x,m);
        creare(2*p+1,m+1,y);
        h[p]=h[2*p]+h[2*p+1];
    }
}
int query(int p,int x,int y,int val)
{
    int m=(x+y)>>1;
    if (x==y) return x;
    else
    if (h[2*p]>=val) return query(2*p,x,m,val);
    else return query(2*p+1,m+1,y,val-h[2*p]);
}
int main()
{
    freopen ("schi.in","r",stdin);
    freopen ("schi.out","w",stdout);
    scanf("%i",&n);
    for (i=1;i<=n;i++)
        scanf("%i",&a[i]);
    creare(1,1,n);
    for (i=n;i>0;i--)
    {
        x=query(1,1,n,a[i]);
        sol[x]=i;
        for (x=poz[x];x;x>>=1) h[x]--;
    }
    for (i=1;i<=n;i++) printf("%i\n",sol[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}