Cod sursa(job #1970219)

Utilizator razvan99hHorhat Razvan razvan99h Data 19 aprilie 2017 01:32:33
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <fstream>
#define DM 30005
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int aib[DM], v[DM], rez[DM], n, m;

void update(int pos, int val)
{
    for(; pos <= n; pos += (pos & (-pos)))
        aib[pos] += val;
}
int sum(int pos)
{
    int rez = 0;
    for(; pos > 0; pos -= (pos & (-pos)))
        rez += aib[pos];
    return rez;
}
int caut_bin_biti(int val) // dubioasa
{
    int pos = 0, step = 1, aux = val;
    for(; step <= n; step <<= 1) ;
    for(; step > 0; step >>= 1)
        if(pos + step <= n)
            if(aib[pos + step ] < val)
            {
                pos += step;
                val -= aib[pos];
            }
    return pos + 1;
}
int caut_bin(int val)
{
    int st = 0, dr = n + 1, mij;
    while(dr - st > 1)
    {
        mij = (st + dr) / 2;
        if(val > sum(mij))
            st = mij;
        else dr = mij;
    }
    return dr;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i];
        update(i, 1); // initial toate pozitiile sunt 'marcate'
    }
    for(int i = n; i >= 1; i--)
    {
        int pos = caut_bin_biti(v[i]); // cautam binar cea de-a v[i] pozitie marcata
        rez[pos] = i;
        update(pos, -1); // apoi 'demarcam' acea pozitie
    }
    for(int i = 1; i <= n; i++)
        fout << rez[i] << '\n';
    return 0;
}