Cod sursa(job #1852759)

Utilizator luci2000lup lucia luci2000 Data 21 ianuarie 2017 10:13:53
Problema Schi Scor 100
Compilator cpp Status done
Runda gym_emag_avansati_2016 Marime 1.03 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

#define lim 30001
int aib[lim],v[lim],rez[lim];
int n;


int lbit(int x)
{
    return x&(-x);
}



void update(int pos, int val)
{
    for(; pos<=n; pos+=lbit(pos))
        aib[pos]+=val;
}



int suma(int pos)
{
    int s=0;
    for(; pos>=1; pos-=lbit(pos))
        s+=aib[pos];
    return s;
}




int caut(int val)
{
    int st=0,dr=n+1,mijl,aux;

    while(st<dr-1)
    {
        mijl=(st+dr)/2;
        aux=suma(mijl);
        if(aux<val)
            st=mijl;
        else
            dr=mijl;
    }
    return dr;
}




int main()
{
    int i,j,poz;
    fin>>n;

    for(i=1; i<=n; ++i)
    {
        fin>>v[i];
        update(i,1);
    }

    for(i=n; i>=1; --i)
    {
        poz=caut(v[i]);
        rez[poz]=i;
        update(poz,-1);
    }

    for(i=1; i<=n; i++)
        fout<<rez[i]<<'\n';

    fin.close();
    fout.close();
    return 0;
}