Cod sursa(job #2099460)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 4 ianuarie 2018 14:03:11
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#define NMAX 30010

using namespace std;

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

int bit(int x)
{
    return (x & -x);
}

int spaces(int x)
{
    int i,sm=0;
    for(i = x;i>=1;i -= bit(i))
        sm+=aib[i];

    return sm;
}

void delete_space(int x)
{
    for(int i = x;i<=n;i += bit(i))
        aib[i]--;
}

int bin_search(int x)
{
    int st = 1,dr = n;
    int mij;

    while(st <= dr)
    {
        mij = st + (dr-st)/2;
        int sp = spaces(mij);
        if(sp < x)
            st = mij + 1;
        else
            dr = mij - 1;
    }

    delete_space(dr+1);
    return dr+1;
}

int main()
{
    int i;
    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] = bit(i);

    for(i=n;i>=1;i--)
        sol[bin_search(v[i])] = i;

    for(i=1;i<=n;i++)
        printf("%d\n",sol[i]);
}