Cod sursa(job #2019646)

Utilizator stefantagaTaga Stefan stefantaga Data 8 septembrie 2017 11:16:29
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>

using namespace std;

ifstream f("schi.in");
ofstream g("schi.out");
int ub(int n)
{
    return (n&(-n));
}
int n,v[30001],aib[30001];
int sum(int x)
{
    int i,s=0;
    for (i=x;i>0;i-=ub(i))
    {
        s+=aib[i];
    }
    return s;
}
void decrementare(int x)
{
    int i;
    for (i=x;i<=n;i+=ub(i))
    {
        aib[i]+=-1;
    }
}
int cautarebinara(int x)
{
    int st,dr,mij,minim=99999999,t;
    st=1;
    dr=n;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        t=sum(mij);
        if (t==x&&mij<minim)
        {
            minim=mij;
        }
        else
        if (sum(mij)>=x)
        {
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    return minim;
}
int sol[30001],z;
int main()
{
    int i;
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>v[i];
    }
    for (i=1;i<=n;i++)
    {
        aib[i]=ub(i);
    }
    for (i=n;i>=1;i--)
    {
        z=cautarebinara(v[i]);
        sol[z]=i;
        decrementare(z);
    }
    for (i=1;i<=n;i++)
    {
        g<<sol[i]<<'\n';
    }
    return 0;
}