Cod sursa(job #1282694)

Utilizator Ionut228Ionut Calofir Ionut228 Data 4 decembrie 2014 17:20:19
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>

using namespace std;

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

int N, AIB[30002], V[30002], sol[30002];

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

int query(int pos)
{
    int sum = 0;
    for (; pos >= 1; pos -= pos & -pos)
        sum += AIB[pos];

    return sum;
}

int bsearch(int x)
{
    int lt = 0, rt = N + 1;

    while (rt - lt > 1)
    {
        int mid = (lt + rt) >> 1;
        int S = query(mid);

        if (S < x)
            lt = mid;
        else
            rt = mid;
    }

    return rt;
}

int main()
{
    fin >> N;
    for (int i = 1; i <= N; ++i)
    {
        fin >> V[i];
        update(i, 1);
    }

    for (int i = N; i >= 1; --i)
    {
        int pos = bsearch(V[i]);
        sol[pos] = i;
        update(pos, -1);
    }

    for (int i = 1; i <= N; ++i)
        fout << sol[i] << '\n';

    fin.close();
    fout.close();
    return 0;
}