Cod sursa(job #2902695)

Utilizator iioaaana777Ghergu Ioana iioaaana777 Data 16 mai 2022 18:33:05
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 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;
            return;
        }

    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] --;
        return;
    }

    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
        if (aint[2 * n] >= val)
            query(2 * n, left, (left + right) /2, val);
        else
            query(2 * n + 1, (left + right) / 2, 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;
}