Cod sursa(job #1522652)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 11 noiembrie 2015 21:26:20
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>

using namespace std;
const int NMAX=30001;
int val, pos, n, aib[NMAX], sol[NMAX], x[NMAX];
void update(int pos,int val)
{
    for(; pos<=n; pos+=pos&(-pos))
        aib[pos]+=val;
}
int query(int pos)
{
    int s=0;
    for(; pos; pos-=pos&(-pos))
        s+=aib[pos];
    return s;
}
int bs(int val)
{
    int l=1, r=n, sol=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(query(mid)>=val)
        {
            sol=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return sol;
}
int main()
{
    int i;
    ifstream in("schi.in");
    ofstream out("schi.out");
    in>>n;
    for(i=1; i<=n; i++)
    {
        in>>x[i];
        update(i, 1);
    }
    for(i=n; i>=1; i--)
    {
        pos=bs(x[i]);
        sol[pos]=i;
        update(pos, -1);
    }
    for(i=1; i<=n; i++)
        out<<sol[i]<<'\n';
    return 0;
}