Cod sursa(job #3005509)

Utilizator Vincent47David Malutan Vincent47 Data 17 martie 2023 03:34:42
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
ifstream cin("schi.in");
ofstream cout("schi.out");

const int dim = 100001;
int n;
int aib[dim], v[dim], sol[dim];


void update(int poz, int val)
{
    for (int i = poz; i <= n; i += i & -i)
        aib[i] += val;
}
int query(int poz)
{
    int sum = 0;
    for (int i = poz; i; i -= i & -i)
        sum += aib[i];
    return sum;
}

int bs(int p)
{
    int l = 1, r = n, m, poz;
    while (l <= r)
    {
        m = (l + r) >> 1;
        if (query(m) >= p)
        {
            poz = m;
            r = m - 1;
        }
        else l = m + 1;
    }
    return poz;
}

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

    for (int i = n; i >= 1; --i)
    {
        int loc = bs(v[i]);
        update(loc, -1);
        sol[loc] = i;
    }
    for (int i = 1; i <= n; ++i)
        cout << sol[i] << '\n';

    return 0;
}