Cod sursa(job #1470874)

Utilizator mirupetPetcan Miruna mirupet Data 12 august 2015 16:15:24
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<cstdio>
#define LSB(x) (x & (-x))
#define DIM (1 << 15)
using namespace std;

int N, poz;
int w[30001], v[30001];
int aib[DIM];

void Update(int, int);
int Query(int);
int Search(int);

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]);
                Update( i, 1);
            }

        for (i = N; i; i--)
        {
            poz = Search(v[i]);
            w[poz] = i;

            Update(poz, -1);
        }

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

void Update(int Pos, int Val)
{
    int i;
    for (i = Pos; i <= N; i += LSB(i))
        aib[i] += Val;
}

int Query(int Pos)
{
    int S = 0, i;
    for (i = Pos; i; i -= LSB(i))
        S += aib[i];

    return S;
}

int Search(int X)
{
    int st = 1, dr = N, mij, S, ans;

    while (st <= dr)
    {
        mij = (st + dr)/2;
        S = Query(mij);

        if (S < X)
            st = mij + 1;
        else
            if (S > X)
                dr = mij - 1;
        else
            ans = mij, dr = mij - 1;

    }

    return ans;
}