Cod sursa(job #1146325)

Utilizator a96tudorAvram Tudor a96tudor Data 18 martie 2014 21:12:46
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<cstdio>
#define ub(x) (x&(-x))
using namespace std;
int V[30010],A[30010],AIB[30010],N,p;
inline int Qwerry(int x)
{
    int S=0;
    for (int i=x;i>0;i-=ub(i)) S+=AIB[i];
    return S;
}
inline void Refresh(int x)
{
    for (int i=x;i<=N;i+=ub(i)) AIB[i]--;
}
inline void BinSearch(int x, int y, int NR)
{
    int st=x,dr=y;
    while (st<=dr)
    {
        int mij=(st+dr)/2;
        int val=Qwerry(mij);
        if (val>NR) dr=mij-1;
        if (val<NR) st=mij+1;
        if (val==NR && mij<p) p=mij;
            else if (val==NR) dr=mij-1;
    }
}
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&N);
    for (int i=1;i<=N;++i)
        scanf("%d",&V[i]), AIB[i]=ub(i);
    for (int i=N;i>=1;--i)
    {
        p=N+1;
        BinSearch(1,N,V[i]);
        A[p]=i;
        Refresh(p);
    }
    for (int i=1;i<=N;++i) printf("%d\n",A[i]);
    fclose(stdin); fclose(stdout);
    return 0;
}