Cod sursa(job #1687316)

Utilizator MaraaMMihali Mara MaraaM Data 12 aprilie 2016 19:42:13
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
#define zeros(x) ((x^(x-1))&x)
#define NMax 30005
int aib[NMax], a[NMax],cls[NMax];
int N;
void update_aib(int,int);
int query_aib(int);
int cautare_binara(int);
void read();
void solve();
int main()
{
    read();
    solve();
    return 0;
}
void read()
{
    f>>N;
    for(int i=1;i<=N;i++) update_aib(i,1);
    for(int i=1;i<=N;++i)
f>>a[i];

}
void solve()
{
    int p;
    for(int i=N;i>0;--i)
    {
        p=cautare_binara(a[i]);
        cls[p]=i;
        update_aib(p,-1);

    }
    for(int i=1;i<=N;i++)
        g<<cls[i]<<'\n';
}
void update_aib(int poz,int val)
{
    for(int i=poz;i<=N;i+=zeros(i))
        aib[i]+=val;
}
int query_aib(int poz)
{    int s=0;
    for(int i=poz;i>0;i-=zeros(i))
        s+=aib[i];
        return s;
}
int cautare_binara(int s)
{
    int st,dr,m,sum,sol;
    st=1; dr=N; sol=-1;
    while(st<=dr)
    {
        m=(st+dr)/2;
        sum=query_aib(m);
        if(sum==s)
        {
            sol=m;
            dr=m-1;

        }
        else if(sum>s) dr=m-1;
        else st=m+1;
    }
    return sol;
}