Cod sursa(job #1425670)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 27 aprilie 2015 21:15:33
Problema Schi Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 1.01 kb
# include <cstdio>
# define ub(x) (x&(-x))

using namespace std;

int n,x;
int a[30005], aib[30005], rez[30005];

void down(int x)

{
    int i;

    for (i = x; i <= n; i += ub(i)) aib[i]--;

}

int suma (int x)

{
    int i, sum = 0;
    for (i = x; i > 0; i -= ub(i)) sum += aib[i];

    return sum;
}

int cautbin(int x) {
    int st = 1, dr = n, mij;
    int Min = 999999999;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (suma(mij) == x && mij < Min) Min = mij;
            else if (suma(mij) < x)  st = mij + 1;
                else dr = mij - 1;
        }
    return Min;
}
int main ()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int i;

    scanf("%d",&n);

    for (i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        aib[i] = ub(i);
    }
    for (i = n; i >= 1; i--) {
        x = cautbin(a[i]);
        rez[x] = i;
        down(x);
    }
    for (i = 1; i <= n; i++)
        printf("%d\n",rez[i]);


return 0;
}