Cod sursa(job #1508137)

Utilizator EpictetStamatin Cristian Epictet Data 22 octombrie 2015 12:41:49
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>

using namespace std;

int n;
short sum, Data[30010], Sol[30010], ARBI[90010];

void Update(int nod, int left, int right, int poz, short value)
{
    if (left == right)
    {
        ARBI[nod] += value;
        return;
    }

    int mid = (left + right) >> 1;
    if (poz <= mid)
    {
        Update((nod << 1), left, mid, poz, value);
    }
    else
    {
        Update((nod << 1) + 1, mid + 1, right, poz, value);
    }
    ARBI[nod] = ARBI[(nod << 1)] + ARBI[(nod << 1) + 1];
}

int Binary_Search(int value)
{
    int i = 1, st = 1, dr = n;

    while (st < dr)
    {
        if (ARBI[(i << 1)] >= value)
        {
            dr = (st + dr) >> 1;
            i <<= 1;
        }
        else
        {
            st = ((st + dr) >> 1) + 1;
            value -= ARBI[i * 2];
            i = i * 2 + 1;
        }
    }

    return st;
}

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);

    scanf("%d", &n);
    for (short i = 1; i <= n; i++)
    {
        scanf("%hd", &Data[i]);
        Update(1, 1, n, i, 1);
    }

    for (short i = n ; i >= 1; i--)
    {
        int poz = Binary_Search(Data[i]);
        Sol[poz] = i;
        Update(1, 1, n, poz, -1);
    }

    for (short i = 1; i <= n; i++) printf("%hd\n", Sol[i]);
    return 0;
}