Cod sursa(job #1497119)

Utilizator ipus1Stefan Enescu ipus1 Data 6 octombrie 2015 08:49:11
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<cstdio>
int v[30001],s[30001],sol[30001];
int lsb(int x)
    {return (x&(-x));
    }
int main ()
{freopen ("schi.in","r",stdin);
freopen ("schi.out","w",stdout);
int n,i,j,k,x,q,c1,c2,pp;
scanf("%d",&n);
for(i=1;i<=n;i++)
    scanf("%d",&s[i]);
for(i=1;i<=n;i++)
    {j=i;
    while(j<=n)
        {v[j]++;
        j+=lsb(j);
        }
    }
for(i=n;i>=1;i--)
    {c1=1;
    c2=n;
    while(c1<=c2)
        {k=(c1+c2)/2;
        q=0;
        j=k;
        while(j>0)
            {q+=v[j];
            j-=lsb(j);
            }
        if(q==s[i])
            {pp=k;
            c2=k-1;
            }
        else
            if(q<s[i])
                c1=k+1;
            else
                c2=k-1;
        }
    k=pp;
    sol[k]=i;
    j=k;
    while(j<=n)
        {v[j]--;
        j+=lsb(j);
        }
    }
for(i=1;i<=n;i++)
    printf("%d\n",sol[i]);
return 0;
}