Cod sursa(job #2803125)

Utilizator PopaMihaimihai popa PopaMihai Data 19 noiembrie 2021 15:42:55
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>
#define ub(x) (x & (-x))
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");

constexpr int NMAX = 3e4 + 3;

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

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

int query(int x)
{
    int ans = 0;
    for(int i = x; i > 0; i -= ub(i))
        ans += aib[i];
    return ans;
}

int cb(int a)
{
    int l = 1, r = n, mid, poz = 0;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        if(query(mid) >= a)
            poz = mid, r = mid - 1;
        else l = mid + 1;
    }
    return poz;
}

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

    for(int i = n; i > 0; i--)
    {
        int a = cb(v[i]);
        clasament[a] = i;
        update (a, -1);
    }

    for(int i = 1; i <= n; i++)
        fout << clasament[i] << '\n';

    return 0;
}