Cod sursa(job #1140855)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 12 martie 2014 12:22:25
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<cstdio>
#define zeros(x) (x&(-x))
using namespace std;

int poz[30002],aib[30002],a[30002],i,n,st,dr,mij,valeur,mn;

void scadd(int pos)
{
    int i;
    for(i=pos;i<=n;i+=zeros(i))
    {
        aib[i]--;
    }
}

int computionare(int pos)
{
    int i,s=0;
    for(i=pos;i>=1;i-=zeros(i))
    {
        s+=aib[i];
    }
    return s;
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&poz[i]);
        aib[i]=zeros(i);
    }
    for(i=n;i>=1;i--)
    {
        st=1;
        dr=n;
        mn=n+1;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            valeur=computionare(mij);
            if(valeur>poz[i])
            {
                dr=mij-1;
            }
            if(valeur<poz[i])
            {
                st=mij+1;
            }
            if(valeur==poz[i] && mij<mn)
            {
                mn=mij;
            }
            else
            if (valeur==poz[i])
            {
                dr=mij-1;
            }
        }
        a[mn]=i;
        scadd(mn);
    }
    for(i=1;i<=n;i++)
    {
        printf("%d\n",a[i]);
    }
    return 0;
}