Cod sursa(job #1268482)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 20 noiembrie 2014 23:29:42
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>

using namespace std;
int n,aib[30005],v[30005],poz[30005];
int lsb(int x)
{
    return (x&(-x));
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}

int query(int poz)
{
    int s=0;
    while(poz)
    {
        s+=aib[poz];
        poz-=lsb(poz);
    }
    return s;
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int i,in,sf,mij,last;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);

    poz[v[n]]=n;
    update(v[n],1);

    for(i=n-1;i>=1;i--)
    {
      last=-1;
      in=v[i]+query(v[i]);
      sf=n;
      //printf("%d ",nr);
        if(v[in]==0)
        {
            update(in,1);
            poz[in]=i;
        }
        else
        {
            while(in<=sf)
            {
                mij=(in+sf)>>1;
                if(query(mij)+v[i]<=mij)
                {
                    last=mij;
                    sf=mij-1;
                }
                else in=mij+1;
            }


            update(last,1);
            poz[last]=i;
        }

    }

    for(int j=1;j<=n;j++) printf("%d\n",poz[j]);

    return 0;
}