Cod sursa(job #1038078)

Utilizator cbanu96Banu Cristian cbanu96 Data 20 noiembrie 2013 23:12:52
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include <vector>

#define FILEIN "schi.in"
#define FILEOUT "schi.out"
#define NMAX 30005

using namespace std;

int N;
vector<int> V;


int AIB[NMAX], sol[NMAX];

int aib_query(int idx)
{
    int sum = 0;

    while (idx)
    {
        sum += AIB[idx];
        idx -= (idx & -idx);
    }

    return sum;
}

void aib_update(int idx, int val)
{
    while (idx <= N)
    {
        AIB[idx] += val;
        idx += (idx & -idx);
    }
}

int bsearch(int k, int left, int right)
{
    int mid, rez = 0;

    while ( left <= right )
    {
        mid = (left+right)/2;
        if (aib_query(mid) >= V[k]) {
            rez = mid;
            right = mid-1;
        } else {
            left = mid+1;
        }
    }

    return rez;
}

int main()
{
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d", &N);
    V.push_back(0);
    for ( int i = 1, x; i <= N; i++ )
    {
        scanf("%d", &x);
        V.push_back(x);
        aib_update(i, 1);
    }

    for ( int i = N; i; --i)
    {
        int pop = bsearch(i, 1, N);

        sol[pop] = i;
        aib_update(pop, -1);
    }

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

    return 0;
}