Cod sursa(job #1551150)

Utilizator edicCiuculescu Eduard edic Data 15 decembrie 2015 11:07:12
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<cstdio>
using namespace std;
int v[60001],ai[60001],r[60001],k[60001],nx[60001],c[60001];
void aib(int h,int n)
{
    int i;
    int ch=h;
    while(ch!=n+1)
    {
        ai[ch]++;
        ch=k[ch]+1;
    }
}
int raib(int h,int n)
{
    int ch=h;
    int r=0;
    while(ch!=0)
    {
        r+=ai[ch];
        ch=nx[ch];
    }
    return r;
}
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int n,i,ki,dr=0,x;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        ki=n-i+1;
        k[i]=1;
        while(ki%2==0)
        {
            ki/=2;
            k[i]*=2;
        }
        k[i]=k[i]+i-1;
    }
    dr++;
    c[dr]=1;
    for(i=2;i<=n;i++)
    {
        while(k[c[dr]]<i)
            dr--;
        nx[i]=c[dr];
        dr++;
        c[dr]=i;
    }
    for(i=n;i>=1;i--)
    {
        x=v[i]+raib(v[i],n);
        while(r[x]!=0)
            x++;
        r[x]=i;
        aib(v[i],n);
    }
    for(i=1;i<=n;i++)
    {
        printf("%d ",r[i]);
    }
    return 0;
}