Cod sursa(job #2986062)

Utilizator matei.tudoseMatei Tudose matei.tudose Data 27 februarie 2023 17:41:39
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <cmath>
using namespace std;

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

int nrSchiori, pozitie[30005], fenwickTree[30005], schiori[30005];

int getLSB(int x)
{
    return (x & (-x));
}

void update(int poz, int val)
{
    for (; poz <= nrSchiori; poz += getLSB(poz))
        fenwickTree[poz] += val;
}

int query(int poz)
{
    int sum = 0;
    for (; poz > 0; poz -= getLSB(poz))
        sum += fenwickTree[poz];
    return sum;
}

// Gasim al x-lea loc liber in clasament si il marcam ca ocupat
int rezolvare(int x)
{
    int pozitieInFenwick = 0;
    for (int i = log2(nrSchiori); i >= 0; i--)
    {
        int pozitiePosibila = pozitieInFenwick + (1 << i);
        if (pozitiePosibila <= nrSchiori && fenwickTree[pozitiePosibila] < x)
        {
            pozitieInFenwick = pozitiePosibila;
            x -= fenwickTree[pozitieInFenwick];
        }
    }
    pozitieInFenwick++;
    // Marcam pozitia din Fenwick ca fiind ocupata, asa ca anulam existenta locului disponibil
    update(pozitieInFenwick, -1);
    return pozitieInFenwick;
}

int main()
{
    fin >> nrSchiori;
    // Cream pozitiile in clasament pentru schiori
    for (int i = 1; i <= nrSchiori; i++)
        update(i, 1);
    for (int i = 1; i <= nrSchiori; i++)
        fin >> schiori[i];
    for (int i = nrSchiori; i > 0; i--)
        pozitie[rezolvare(schiori[i])] = i;
    for (int i = 1; i <= nrSchiori; i++)
        fout << pozitie[i] << "\n";
    return 0;
}