Cod sursa(job #1833150)

Utilizator crazylamaRiclea Andrei crazylama Data 21 decembrie 2016 19:57:51
Problema Schi Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <vector>
using namespace std;

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

vector<int> arbInt, v, sol;

void updateArbInt(int st, int dr, int x, int poz, int nod)
{
    if (st == dr)
    {
        arbInt[nod] = x;
        return;
    }
    int mij = st + (dr - st) / 2;
    if (poz <= mij)
        updateArbInt(st, mij, x, poz, 2 * nod);
    else
        updateArbInt(mij + 1, dr, x, poz, 2 * nod + 1);
    arbInt[nod] = arbInt[2 * nod] + arbInt[2 * nod + 1];
}

int searchArbInt(int st, int dr, int x, int nod)
{
    if (st == dr)
        return st;
    int mij = st + (dr - st) / 2;
    if (x > arbInt[2 * nod])
        return searchArbInt(mij + 1, dr, x - arbInt[2 * nod], 2 * nod + 1);
    return searchArbInt(st, mij, x, 2 * nod);
}

int main()
{
    int n;
    f >> n;
    v.resize(n + 1);
    sol.resize(n + 1);
    arbInt.resize(4 * n + 1);
    for (int i = 1; i <= n; ++i)
    {
        f >> v[i];
        updateArbInt(1, n, 1, i, 1);
    }
    for (int i = n; i > 0; --i)
    {
        int poz = searchArbInt(1, n, v[i], 1);
        sol[poz] = i;
        updateArbInt(1, n, 0, poz, 1);
    }
    for (int i = 1; i <= n; ++i)
        g << sol[i] << "\n";
    f.close();
    g.close();
    return 0;
}