Cod sursa(job #2902777)

Utilizator iioaaana777Ghergu Ioana iioaaana777 Data 16 mai 2022 20:00:31
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#define NMAX 30002
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");

int N, aint[4 * NMAX], poz[NMAX], v[NMAX];

void create(int n, int left, int right)
{
    if (left == right)
        aint[n] = 1;
    else
    {
         create(2 * n, left, (left + right) / 2);
         create(2 * n + 1, (left + right) / 2 + 1, right);
         aint[n] = aint[2 * n] + aint[2 * n + 1];

    }

}

void update(int n, int left, int right, int val)
{
    if(left == right)
        aint[n] --;
    else
    {
        if(val <= (left + right) / 2)
            update(2 * n, left, (left + right) / 2, val);
        else
            update(2 * n + 1, (left + right) / 2 + 1, right, val);

        aint[n] = aint[2 * n] + aint[2 * n + 1];
    }

}
int query(int n, int left, int right, int val)
{
    if (left == right)
        return left;

    else
    {
        int m = (left + right) / 2;

        if (aint[2 * n] >= val)
            return query(2 * n, left, m, val);
        else
            return query(2 * n + 1 ,m + 1, right, val - aint[2 * n]);
    }

}

int main()
{
    fin >> N;

    for (int i = 1; i <= N; ++i)
        fin >> v[i];

    create(1, 1, N);

    for (int i = N; i >= 1; --i)
    {
        int k = query(1, 1, N, v[i]);
        update(1, 1, N, k);
        poz[k] = i;
    }

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

    return 0;
}