Cod sursa(job #1259988)

Utilizator Yasin_ibraimIbraim Yasin Yasin_ibraim Data 10 noiembrie 2014 19:30:08
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>

int n, v[30005];
int aib[30005], sol[30005];

void update(int x)
{
    while (x<=n)
    {
        ++aib[x];
        x += x&(x-1)^x;
    }
}

int query(int x)
{
    int sum = 0;

    while (x)
    {
        sum += aib[x];
        x -= x&(x-1)^x;
    }
    return sum;
}

int bsearch(int x)
{
    int li=x+query(x), ls=n;
    int sol = ls;

    while (li<=ls)
    {
        int m=(li+ls)/2;

        if (m-query(m)>=x)
        {
            sol = m;
            ls = m-1;
        }
        else
        {
            li = m+1;
        }
    }
    return sol;
}

int main()
{
    FILE *fin,*fout;
    fin=fopen("schi.in", "r",);
    fout=fopen("schi.out", "w", stdout);

    scanf("%d", &n);
    for (int i=1; i<=n; ++i)
    {
        scanf("%d", &v[i]);
    }
    for (int i=n; i; --i)
    {
        int pos = bsearch(v[i]);
        sol[bsearch(v[i])] = i;
        update(pos);
    }
    for (int i=1; i<=n; ++i)
    {
        printf("%d\n", sol[i]);
    }
    return 0;
}