Cod sursa(job #2954543)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 14 decembrie 2022 19:18:04
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>

using namespace std;

const int NMAX = 30000;

int v[1 + NMAX];

int aint[1 + 4 * NMAX];

int sol[1 + NMAX];

void buildAint(int index, int st, int dr)
{
    if (st == dr)
    {
        aint[index] = 1;

        return;
    }

    int mij = (st + dr) / 2;

    int fiuSt = 2 * index;
    int fiuDr = 2 * index + 1;

    buildAint(fiuSt, st, mij);
    buildAint(fiuDr, mij + 1, dr);

    aint[index] = aint[fiuSt] + aint[fiuDr];
}

void updateAint(int index, int st, int dr, int poz)
{
    if (st == dr)
    {
        aint[index] = 0;

        return;
    }

    int mij = (st + dr) / 2;

    int fiuSt = 2 * index;
    int fiuDr = 2 * index + 1;

    if (poz <= mij)
        updateAint(fiuSt, st, mij, poz);
    else
        updateAint(fiuDr, mij + 1, dr, poz);

    aint[index] = aint[fiuSt] + aint[fiuDr];
}

int queryAint(int index, int st, int dr, int poz)
{
    if (st == dr)
        return st;

    int mij = (st + dr) / 2;

    int fiuSt = 2 * index;
    int fiuDr = 2 * index + 1;

    if (poz <= aint[fiuSt])
        return queryAint(fiuSt, st, mij, poz);
    else
        return queryAint(fiuDr, mij + 1, dr, poz - aint[fiuSt]);
}

int main()
{
    ios_base::sync_with_stdio(false);

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

    int n;
    in >> n;

    for (int i = 1; i <= n; i++)
        in >> v[i];

    buildAint(1, 1, n);

    for (int i = n; i >= 1; i--)
    {
        int poz = queryAint(1, 1, n, v[i]);
        sol[poz] = i;
        updateAint(1, 1, n, poz);
    }

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

    in.close();
    out.close();

    return 0;
}