Cod sursa(job #1569986)

Utilizator elevenstrArina Raileanu elevenstr Data 16 ianuarie 2016 08:58:33
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>

using namespace std;

ifstream cin("schi.in");
ofstream cout("schi.out");

const int LIM=30005;
int n, v[LIM], aib[LIM], sol[LIM];
void update(int idx)
{
    while(idx<=n)
    {
        aib[idx]--;
        idx+=(idx & -idx);
    }
}
int query(int val)
{
    int idx=1, ans=0;
    while(idx*2<=n) idx*=2;
    while(idx>0)
    {
        if(idx+ans<=n)
            if(val>=aib[idx+ans])
            {
                val-=aib[idx+ans];
                ans+=idx;
            }
        idx/=2;
    }
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; ++i)
        aib[i]=(i & -i);
    for(int i=1; i<=n; ++i)
        cin>>v[i];
    for(int i=n; i>=1; --i)
    {
        int ans=query(v[i]-1);
        sol[ans+1]=i;
        update(ans+1);
    }
    for(int i=1; i<=n; ++i)
        cout<<sol[i]<<'\n';
    return 0;
}