Cod sursa(job #1855090)

Utilizator raulrusu99Raul Rusu raulrusu99 Data 23 ianuarie 2017 13:54:24
Problema Schi Scor 100
Compilator cpp Status done
Runda gym_emag_avansati_2016 Marime 1.16 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
#define N_MAX 30005
int aib[N_MAX], v[N_MAX], n, rez[N_MAX];

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

int query(int pos)
{
    int sum = 0;
    for(; pos > 0; pos -= pos & (-pos))
        sum += aib[pos];
    return sum;
}

int sum(int left, int right)
{
    return query(right) - query(left - 1);
}

int Search(int val)
{
    int i, step;

    for ( step = 1; step < n; step <<= 1 );

    for( i = 0; step; step >>= 1 )
    {
        if( i + step <= n)
        {
            if( val >= aib[i+step] )
            {
                i += step, val -= aib[i];
            }
        }
    }
    return i;
}

int main()
{
    f >> n;
    for(int i = 1; i <= n; i++)
        f >> v[i];

    for(int i = 1; i <= n; i++)
        update(i,1);

    for(int i = n; i >= 1; i--)
    {
        int pos = Search(v[i] - 1);
        update(pos + 1, -1);
        rez[pos + 1] = i;
    }
    for (int i = 1; i <= n; i++)
        g << rez[i] << "\n";
    return 0;
}