Cod sursa(job #1152868)

Utilizator gbi250Gabriela Moldovan gbi250 Data 25 martie 2014 00:32:07
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#define zeros( x ) ( x ^ (x - 1) & x )
#define SIZE 30004
using namespace std;

int n, v[SIZE], AIB[SIZE], sol[SIZE];


inline void read();
inline void solve();
inline void write();
inline void update(int, int);
inline int search_val(int, int, int);
inline int AIB_sum(int);

int main()
{
    read();
    solve();
    write();
    return 0;
}

inline void read()
{
    freopen("schi.in", "r", stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &v[i]);
        update(i, 1);
    }
}

inline void solve()
{
    for(int i = n; i >= 1; --i)
    {
        int index = search_val(v[ i ], 1, n);
        sol[ index ] = i;
        update(index, -1);
    }
}

inline void write()
{
    freopen("schi.out", "w", stdout);

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

inline void update(int index, int value)
{
    for(int i = index; i <= n; i += zeros(i) )
        AIB[ i ] += value;
}

inline int AIB_sum(int index)
{
    int sum = 0;
    for(int i = index; i >= 1; i -= zeros(i))
        sum += AIB[ i ];
    return sum;
}

inline int search_val(int value, int left, int right)
{
    int pos = -1;
    while( left <=  right)
    {
        int middle = (left + right) >> 1;

        if( AIB_sum( middle ) >= value )
        {
            right = middle - 1;
            pos = middle;
        }
        else
            left = middle + 1;
    }
    return pos;
}