Cod sursa(job #1564104)

Utilizator danstefanDamian Dan Stefan danstefan Data 8 ianuarie 2016 13:46:39
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>
#define Ub(x) x&(-x)
using namespace std;
int x,aib[30010],n,v[30010],srb[30010];
void Add(int pos,int val)
{
    for(int i=pos; i<=n; i+=Ub(i))
        aib[i]+=val;
}
int Suma(int pos)
{
    int s=0;
    for(int i=pos; i>=1; i-=Ub(i))
        s+=aib[i];
    return s;
}
int main()
{
    freopen("schi.in","r",stdin);
    ofstream g ("schi.out");
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d",&v[i]);
        Add(i,1);
    }
    for(int i=n; i>=1; --i)
    {
        int l=1;
        int r=n;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(Suma(mid)<v[i])l=mid+1;
            else r=mid-1;
        }
        srb[l]=i;
        Add(l,-1);
    }
    for(int i=1;i<=n;++i)
        g<<srb[i]<<'\n';
    return 0;}