Cod sursa(job #2804225)

Utilizator Stefan_DomuncoStefan Domunco Stefan_Domunco Data 21 noiembrie 2021 10:26:21
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 3e4+5;
int clasament_partial[NMAX], AIB[NMAX], sol[NMAX], n;

void create_aib()
{
    int i;
    for(i = 1; i <= n; ++i)
    {
        int next = i + (i & -i);
        if(next <= n)
            AIB[next] += AIB[i];
    }
}

void update_aib(int poz, int val)
{
    while(poz <= n)
    {
        AIB[poz] += val;
        poz += poz & -poz;
    }
}

int sum_aib(int poz)
{
    int sum = 0;
    while(poz > 0)
    {
        sum += AIB[poz];
        poz -= poz & -poz;
    }
    return sum;
}

int bs_poz(int val)
{
    int st, dr, mij, sol, aux;
    st = 1;
    dr = n;

    while(st <= dr)
    {
        mij = (st + dr) / 2;
        aux = sum_aib(mij);
        if(aux == val)
            sol = mij, dr = mij - 1;
        else if(aux > val)
            dr = mij - 1;
        else st = mij + 1;
    }

    return sol;
}

int main()
{
    int i;
    fin >> n;
    for(i = 1; i <= n; ++i)
        fin >> clasament_partial[i], AIB[i] = 1;

    create_aib();

    for(i = n; i >= 1; --i)
    {
        int aux = bs_poz(clasament_partial[i]);
        sol[aux] = i;
        update_aib(aux, -1);
    }

    for(i = 1; i <= n; ++i)
        fout << sol[i] << '\n';
    return 0;
}