Cod sursa(job #1140849)

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

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

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;
        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])
            {
                while(valeur==poz[i])
                {
                    valeur=computionare(mij);
                    if(valeur==poz[i])
                    {
                        mij--;
                    }
                    else
                    {
                        mij++;
                        break;
                    }
                }
                a[mij]=i;
                break;
            }
        }
        scadd(mij);
    }
    for(i=1;i<=n;i++)
    {
        printf("%d\n",a[i]);
    }
    return 0;
}