Cod sursa(job #1275115)

Utilizator sebinechitasebi nechita sebinechita Data 24 noiembrie 2014 19:47:44
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
#define MAX 30100
int n, AIB[MAX], a[MAX], rez[MAX];

void update(int poz, int val)
{
    while(poz<=n)
    {
        AIB[poz]+=val;
        poz+=(poz&(-poz));
    }
}

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

int caut_bin(int val)
{

    int st, dr, mid, d;
    st=1;
    dr=n;
    while(st<dr)
    {

        mid=(st+dr)/2;
        d=sum(mid);
        if(d>val)
        {
            dr=mid-1;
        }
        else if(d==val)
            dr=mid;
        else
            st=mid+1;
    }
    return st;
}

int main()
{
    fin>>n;
    int i;
    for(i=1;i<=n;i++)
    {
        update(i, 1);
        fin>>a[i];
    }
    for(i=n;i>=1;i--)
    {
        int x=caut_bin(a[i]);
        rez[x]=i;
        update(x, -1);
    }
    for(i=1;i<=n;i++)
    {
        fout<<rez[i]<<"\n";
    }
}