Cod sursa(job #856685)

Utilizator ericptsStavarache Petru Eric ericpts Data 16 ianuarie 2013 20:47:22
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");
const int maxn = 30003;
int v[maxn];
int show[maxn];
int aib[maxn];
int n;
inline const int lsb(const int &a)
{
    return (a & (-a));
}

void update(int poz,int val)
{
    for(;poz <= n ; poz += lsb(poz))
        aib[poz] += val;
}
int query(int poz)
{
    int ret = 0;
    for(;poz;poz -= lsb(poz))
        ret += aib[poz];
    return ret;
}

int bs(const int &look)
{
    int i,step;
    for(i=n,step=1<<16;step;step>>=1)
        if(i-step >= 1 && query(i-step) >= look)
            i -= step;
    return i;
}

int main()
{
    int i;
    int poz;
    in >> n;
    for(i=1;i<=n;++i)
    {
        in >> v[i];
        update(i,1);
    }
    for(i=n;i;--i)
    {
        poz = bs(v[i]);
        show[poz] = i;
        update(poz,-1);
    }
    for(i=1;i<=n;++i)
        out << show[i] << "\n";

    return 0;
}