Cod sursa(job #1850266)

Utilizator andysoloAndrei Solo andysolo Data 18 ianuarie 2017 14:14:41
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#define NMAX 30000
#define lb(x) x&(-x)

using namespace std;

int N,AiB[NMAX+5],p,v[NMAX+5],loc[NMAX+5];

int getAiB(int);

int bin(int x)
{
    int f=1,s=N;

    while(f<=s)
    {
        int m=(f+s)>>1;
        int sum=getAiB(m);
        if(sum==x && f==s)
            return m;
        else if(sum<x)
            f=m+1;
        else s=m;
    }
}

int getAiB(int p)
{
    int s=0;
    for(int i=p;i>=1;i-=lb(i))
        s+=AiB[i];
    return s;
}

void setAiB(int p,int k)
{
    for(int i=p;i<=N;i+=lb(i))
        AiB[i]+=k;
}
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);

    scanf("%d",&N);

    for(int i=1;i<=N;i++){
        scanf("%d",&v[i]);
        setAiB(i,1);
    }

    for(int i=N;i>=1;i--)
    {
        int x=bin(v[i]);
        setAiB(x,-1);
        loc[x]=i;
    }

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

    return 0;
}