Cod sursa(job #3241859)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 5 septembrie 2024 12:25:34
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

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

#define lsb(i) (i & (-i))

const int NMAX = 30001;
int v[NMAX], aib[NMAX], locuri[NMAX], n;

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

int sum(int poz)
{
    int s = 0;
    for(int i = poz; i >= 1; i -= lsb(i))
        s += aib[i];
    return s;
}

int find_poz(int ranking)
{
    int st = 1, dr = n, poz = n + 1;
    while(st <= dr)
    {
        int mid = (st + dr) / 2;
        if(sum(mid) < ranking)
            st = mid + 1;
        else
        {
            poz = mid;
            dr = mid - 1;
        }
    }
    update(-1, poz);
    return poz;
}

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

    for (int i = n; i >= 1; i--)
        locuri[find_poz(v[i])] = i;

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

    return 0;
}