Cod sursa(job #2489297)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 8 noiembrie 2019 13:18:36
Problema Schi Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#define NMAX 30005
#define ub(x) (x & -x)

using namespace std;

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

int aib[NMAX], clas[NMAX], v[NMAX], n;

void update(int p)
{
    for (int i = p; i <= n; i += ub(i))
        aib[i]++;
}

int64_t query(int p)
{
    int64_t suma = 0;
    for (int i = p; i >= 1; i -= ub(i))
        suma += aib[i];
    return suma;
}

int bsearch(int p, int u, int key)
{
    int m;
    while (p <= u)
    {
        m = (p + u) / 2;
        if(m - query(m) <= key) p = m + 1;
        else u = m - 1;
    }
    m = (p + u) / 2;
    if (m - query(m) > key) m--;
    while (m - query(m) == key && m) m--;
    return m + 1;
}


int main()
{
    fin >> n;

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

    for (int i = n; i >= 1; --i)
    {
        int p = bsearch(v[i], n, v[i]);
        clas[p] = i;
        update(p);
    }

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

    return 0;
}