Cod sursa(job #1511953)

Utilizator PletoPletosu Cosmin-Andrei Pleto Data 27 octombrie 2015 13:42:40
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>

#define nrz_p2(x) x&(-x)

using namespace std;

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

int N,V[30010],AIB[30010],SOL[30010];

void actualizare(int poz,int val)
{
    while(poz<=N)
    {
        AIB[poz]+=val;
        poz+=nrz_p2(poz);
    }
}

int interogare(int poz)
{
    int s=0;
    while(poz)
    {
        s+=AIB[poz];
        poz-=nrz_p2(poz);
    }
    return s;
}

int cautare_binara(int val)
{
    int st=1,dr=N,sol=N;
    while(st<=dr)
    {
        int m=(st+dr)/2;
        if(interogare(m)>=val)
        {
            sol=m;
            dr=m-1;
        }
        else st=m+1;
    }
    return sol;
}

void citire()
{
    in>>N;
    for(int i=1;i<=N;i++)
    {
        in>>V[i];
        actualizare(i,1);
    }
}

int main()
{
    citire();
    for(int i=N;i>0;i--)
    {
        int p=cautare_binara(V[i]);
        SOL[p]=i;
        actualizare(p,-1);
    }
    for(int i=1;i<=N;i++)
    {
        out<<SOL[i]<<'\n';
    }
    return 0;
}