Cod sursa(job #1680442)

Utilizator binicBinica Nicolae binic Data 8 aprilie 2016 19:25:20
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,x,r,v[30004],ras[30004];
int a[90004];
void dfs(int nod, int st, int dr)
{
    if(st==dr)
    {
        a[nod]=1;
        return ;
    }
    int mij=(st+dr)/2;
    dfs(nod*2,st,mij);
    dfs(nod*2+1,mij+1,dr);
    a[nod]=a[nod*2]+a[nod*2+1];
}
void update(int nod, int st, int dr, int poz, int val)
{
    if(st==dr)
    {
        a[nod]=val;
        return ;
    }
    int mij=(st+dr)/2;
    if(mij>=poz)update(nod*2,st,mij,poz,val);
    else update(nod*2+1,mij+1,dr,poz,val);
    a[nod]=a[nod*2]+a[nod*2+1];
}
void query(int nod, int st, int dr, int val)
{
    if(st==dr)
    {
        r=st;
        return ;
    }
    int mij=(st+dr)/2;
    if(a[nod*2]>=val)query(nod*2,st,mij,val);
    else query(nod*2+1,mij+1,dr,val-a[nod*2]);
}
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    dfs(1,1,n);
    for(int i=n;i>=1;i--)
    {
        query(1,1,n,v[i]);
        ras[r]=i;
        update(1,1,n,r,0);
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",ras[i]);
    return 0;
}