Cod sursa(job #213836)

Utilizator Mishu91Andrei Misarca Mishu91 Data 11 octombrie 2008 20:04:12
Problema Schi Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
//varianta cu arbori indexati binar
#include <cstdio>
#include <cstring>

#define step ((k ^(k-1)) & k)
#define MAX_N 30005

int V[MAX_N], A[MAX_N], Sol[MAX_N];
int N, viz[MAX_N];

void citire()
{
    scanf("%d",&N);

    for(int i = 1; i <= N; ++i)
        scanf("%d",V+i);
}

void update(int k, int val)
{
    while(k <= N)
    {
        A[k] += val;
        k += step;
    }
}

int querry(int sum)
{
    int i, pas;
    memset(viz,0,sizeof viz);
    int x = sum, pmin = MAX_N;
    for(pas = 1; pas < N; pas <<= 1);
    int y = pas;

    for(i = 0; pas; pas >>= 1)
        if(i + pas <= N)
            if(sum >= A[i + pas] && (!viz[i+pas]))
            {
                i += pas, sum -= A[i];
                if((!sum) && i < pmin && !(viz[i]))
                    pmin = i, sum = x, viz[i] = 1, i = 0, pas = y;
            }
    return pmin;
}

void solve()
{
    for(int i = 1; i <= N; ++i)
        update(i, 1);

    for(int i = N; i; i--)
    {
        int q = querry(V[i]);
        Sol[q] = i;
        update(q,-1);
    }
    for(int i = 1; i <= N; ++i)
        printf("%d\n",Sol[i]);
}

int main()
{
    freopen("schi.in","rt",stdin);
    freopen("schi.out","wt",stdout);
    citire();
    solve();
}