Cod sursa(job #1425701)

Utilizator delia_99Delia Draghici delia_99 Data 27 aprilie 2015 21:39:36
Problema Schi Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 1 kb
#include <cstdio>
#define NMAX 30010
#define ub(x) (x&(-x))

using namespace std;
int AIB[NMAX],v[NMAX],i,n,sol[NMAX],pos;

int sum(int x)
{
    int i,s=0;
    for(i=x;i>0;i-=ub(i))
      s+=AIB[i];
    return s;
}

int binary_search(int x)
{
    int st=1,dr=n,p,Min=300001,s,m;
    while(st<=dr)
    {
        m=st+(dr-st)/2;
        s=sum(m);
        if(s==x && Min>m)
            Min=m;
        else
        {
            if(s>=x)  dr=m-1;
            else st=m+1;
        }

    }
    return Min;
}

void new_list(int pos)
{
    int i;
    for(i=pos;i<=n;i+=ub(i))
      --AIB[i];
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d\n",&n);
    for(i=1; i<=n; ++i)
    {
        scanf("%d\n",&v[i]);
        AIB[i]=ub(i);
    }
    for(i=n; i>=1; --i)
    {
        pos=binary_search(v[i]);
        sol[pos]=i;
        new_list(pos);

    }
    for(i=1;i<=n;++i)
      printf("%d\n",sol[i]);

    return 0;
}