Cod sursa(job #3322394)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 13 noiembrie 2025 19:26:13
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <string.h>
#define NMAX 30005
#define ub(x) (x & -x)
#include <stdio.h>
#include <ctype.h>

using namespace std;

ofstream fout("schi.out");

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

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

int query(int p)
{
    int 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 (query(m) <= key)
            p = m + 1;
        else
            u = m - 1;
    }

    m = (p + u) / 2;

    if (query(m) > key)
        m--;
    while (query(m) == key && m)
        m--;

    m++;

    if (query(m) == key)
        return m;
    return -1;
}

int main()
{
    ifstream fin("schi.in");

    fin >> n;

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

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

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

    return 0;
}