Cod sursa(job #1509057)

Utilizator Iustin48Ventaniuc Iustin Iustin48 Data 23 octombrie 2015 14:18:48
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#define zero(poz) ((poz^(poz-1))&poz)
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,log,poz,aib[30001],sol[30001],v[30001],x;
int query(int poz)
{
    int s=0;
    for(;poz;poz-=zero(poz))
        s+=aib[poz];
    return s;
}
int bs(int val)
{
    int st=1,dr=n,sol=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(query(mij)>=val)
        {
            sol=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    return sol;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
    {
        f>>v[i];
        poz=i;
        for(;poz<=n;poz+=zero(poz))
            ++aib[poz];
    }
    for(int i=n;i;--i)
    {
        x=v[i];
        poz=bs(x);
        sol[poz]=i;
        for(;poz<=n;poz+=zero(poz))
            --aib[poz];
    }
    for(int i=1;i<=n;++i)
        g<<sol[i]<<'\n';
    g.close();
    return 0;
}