Cod sursa(job #1850224)

Utilizator marumatMatei Marussi Alexandru marumat Data 18 ianuarie 2017 12:58:22
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>

using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int a[30005],aib[30005],i,x,st,dr,mij,n,b[30005];
int UB (int x)
{return x&(-x);
}
void add(int i,int x)
{int j;
    for(j=i;j<=n;j+=UB(j))
      aib[j]+=x;
}
int sum(int x)
{int i,S;
S=0;
    for(i=x;i>0;i-=UB(i))
    S+=aib[i];
    return S;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>b[i];
    for(i=1;i<=n;i++)
    add(i,1);
    for(i=1;i<=n;i++)
    a[i]=0;
    for(i=n;i>=1;i--)
    {
    st=1;dr=n;
    while(st<=dr)
    {mij=(st+dr)/2;
        if(sum(mij)<b[i])st=mij+1;
        else if(sum(mij)>b[i])dr=mij-1;
        else if(sum(mij)==b[i])
        {if(a[mij]==0){
            a[mij]=i;
            add(mij,-1);
            break;
        }
        else dr=mij-1;}
    }
    }
    for(i=1;i<=n;i++)
        g<<a[i]<<'\n';
    return 0;
}