Cod sursa(job #2019683)

Utilizator bebeetarepredescu bebeetare Data 8 septembrie 2017 12:27:15
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#define ub(x) (x&(-x))

using namespace std;
int a[30003],b[30003],aib[30003],j,Min,n,dr,st,m,i;
ifstream f("schi.in");
ofstream g("schi.out");
void scad(int poz)
{
    int i;
    for(i=poz;i<=n;i+=ub(i))
    {
        aib[i]--;
    }
}
int sum(int poz)
{
    int s=0;
    int i;
    for(i=poz;i>0;i-=ub(i))
    {
        s+=aib[i];
    }
    return s;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i];
        aib[i]=ub(i);
    }
    for(j=n;j>=1;j--)
    {
        st=1;
        dr=n;
        Min=n+1;
        while(st<=dr)
        {
            m=(st+dr)/2;
            if(sum(m)==a[j] && Min>m)
            {
                Min=m;
                dr=m-1;
            }
            else if(sum(m)>a[j])
            {
                dr=m-1;
            }
            else
            {
                st=m+1;
            }
        }
        b[Min]=j;
        scad(Min);
    }
    for(j=1;j<=n;j++)
    {
        g<<b[j]<<'\n';
    }
    return 0;
}