Cod sursa(job #1179772)

Utilizator costyrazvyTudor Costin Razvan costyrazvy Data 29 aprilie 2014 11:34:36
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <climits>

#define ub(x) (x&(-x))
#define NMAX 30001

using namespace std;

int A[NMAX],X[NMAX],sol[NMAX];
int N,i,x;

void Decrease(int x)
{
    int i;

    for(i=x;i<=N;i+=ub(i)) A[i]--;
}

int Sum(int poz)
{
    int i=0,T=0;

    for(i=poz; i>0; i-=ub(i)) T+=A[i];

    return T;
}
int binary_search(int x)
{
    int S=1,D=N,M=0,T=0,Minim=INT_MAX;

    while(S<=D)
    {
        M=(S+D)/2;
        T=Sum(M);

        if (T==x && M<Minim) Minim=M;
              else if (T>=x) D=M-1;
                          else S=M+1;
    }

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

    scanf("%d",&N);
    for (i=1; i<=N; ++i) scanf("%d",&X[i]);
    for (i=1; i<=N; ++i) A[i]=ub(i);

    for (i=N; i>=1; --i)
    {
        x=binary_search(X[i]);
        sol[x]=i;
        Decrease(x);
    }

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

    return 0;
}