Cod sursa(job #1504439)

Utilizator zacuscaAlex Iordache zacusca Data 17 octombrie 2015 18:57:36
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
int n, AIB[30001], V[30001], sol[30001];
inline int zero(int x)
{
    return x & (-x);
}
void update(int poz, int val)
{
    for(; poz<=n; poz += zero(poz))
        AIB[poz] += val;
}
int query(int poz)
{
    int s=0;
    for(; poz; poz -= zero(poz))
        s += AIB[poz];
    return s;
}
int bs (int val)
{
    int st = 1, dr = n, sol = n;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if (query (mij) >= val)
        {
            sol = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    return sol;
}

int main ()
{
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> V[i];
        update (i, 1);
    }
    for (int i = n; i; i--)
    {
        int poz = bs (V[i]);
        sol[poz] = i;
        update (poz, -1);
    }
    for (int i = 1; i <= n; i++)
        out << sol[i] << '\n';
    out.close();
    return 0;
}