Cod sursa(job #1850310)

Utilizator anamaria41Raicu Ana anamaria41 Data 18 ianuarie 2017 15:11:27
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <cstdio>

using namespace std;
#define ub(x)(x&(-x))

int n,i,a[30050],aib[30050],b[30050],poz;
void add(int x)
{
    int i=0;
    for(i=x;i<=n;i+=ub(i))
    aib[i]--;
}

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

int bs(int x)
{
    int st=1,dr=n,mid=(st+dr)/2;

    while(st<=dr)
    {
        mid=(st+dr)/2;
        int sm=sum(mid);
        if(sm<x)st=mid+1;
        else dr=mid-1;
    }
    add(dr+1);
    return dr+1;
}
int main()
{

    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);

    scanf("%d",&n);

    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=n;i++) aib[i]=ub(i);

    for(i=n;i>=1;i--)
        b[bs(a[i])]=i;
    for(i=1;i<=n;i++) printf ("%d\n",b[i]);
    return 0;
}