Cod sursa(job #779771)

Utilizator visanrVisan Radu visanr Data 18 august 2012 18:34:15
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;


int N, AIB[30010], sol[30010], v[30010];


void Update(int pos, int val)
{
     for(; pos <= N; pos += (pos & (-pos)))
           AIB[pos] += val;
}

int Query(int pos)
{
    int sum = 0;
    for(; pos; pos -= (pos & (-pos)))
          sum += AIB[pos];
    return sum;
}

int BS(int X)
{
    int i = 0;
    for(int step = (1 << 17); step; step >>= 1)
            if(i + step <= N && Query(i + step) < X)
                 i += step;
    Update(i + 1, -1);
    return i + 1;
}

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    int i;
    scanf("%i", &N);
    for(i = 1; i <= N; i++)
    {
          scanf("%i", &v[i]);
          Update(i, 1);
    }
    for(i = N; i; i--)
          sol[ BS(v[i]) ] = i;
    for(i = 1; i <= N; i++) printf("%i\n", sol[i]);
    return 0;
}