Cod sursa(job #1183007)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 8 mai 2014 12:19:15
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#define lsb(x) (x&(-x))

using namespace std;
int n, i, p, u, mn, x, k, v[30005], aib[30005], a[30005];
void U(int x)
{
    int i;
    for(i=x;i<=n;i+=lsb(i))
        aib[i]--;
}
int Q(int x)
{
    int i, s=0;
    for(i=x;i>=1;i-=lsb(i))
        s+=aib[i];
    return s;
}
int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &n);
    for(i=1;i<=n;i++)
        scanf("%d", &v[i]);
    for(i=1;i<=n;i++)
        aib[i]=lsb(i);
    for(i=n;i>=1;i--)
    {
        p=1;u=n;
        mn=9999999;
        while(p<=u)
        {
            k=p+(u-p)/2;
            x=Q(k);
            if(x==v[i]&&k<mn)
            {
                mn=k;
                u=k-1;
            }
            else if(x>v[i]) u=k-1;
            else p=k+1;
        }
        a[mn]=i;
        U(mn);
    }
    for(i=1;i<=n;i++)
        printf("%d\n", a[i]);
    return 0;
}