Cod sursa(job #1139095)

Utilizator j.loves_rockJessica Joanne Patrascu j.loves_rock Data 10 martie 2014 21:07:18
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <cstdio>
#define bit(i) (i&-i)
using namespace std;

int sol[30001],a[30001],n,nr,poz,i;
int c[30001];
void update(int poz, int val)
{
    for(int i=poz; i<=n; i+=bit(i)) c[i]+=val;
}
int caut(int poz)
{
    int i=0,step,s=0;
    for (i=0,step=1<<16; step; step>>=1)
        if((i+step<=n)&&(c[i+step]+s<poz))
            s+=c[i+step],i+=step;
    return i+1;
}
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for (i=1; i<=n; ++i) scanf("%d",&a[i]);
    for (i=1; i<=n; ++i)
    c[i]=bit(i);
    for (i=n; i>=1; --i)
    {
        poz=caut(a[i]);
        sol[poz]=i;
        update(poz,-1);
    }
    for(int i=1; i<=n; ++i) printf("%d\n",sol[i]);
    return 0;
}