Cod sursa(job #2985171)

Utilizator matei.tudoseMatei Tudose matei.tudose Data 25 februarie 2023 19:39:41
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 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, locuriLibereParcurse = 0;
//    for (int i = log2(nrSchiori); i >= 0; i--)
//    {
//        int pozitiePosibila = pozitieInFenwick + (1 << i);
//        if (fenwickTree[pozitiePosibila] == 0)
//            continue;
//        if (pozitiePosibila <= nrSchiori && fenwickTree[pozitiePosibila] <= x - locuriLibereParcurse)
//        {
//            pozitieInFenwick = pozitiePosibila;
//            locuriLibereParcurse += fenwickTree[pozitieInFenwick];
//        }
//    }
//    // Marcam pozitia din Fenwick ca fiind ocupata, asa ca anulam existenta locului disponibil
//    update(pozitieInFenwick, -1);
//    return pozitieInFenwick;

    int st = 1, dr = nrSchiori, pozitieFenwick;
    while (st <= dr)
    {
        int mid = (st + dr) / 2;
        int locuriLibere = query(mid);
        if (locuriLibere >= x)
            pozitieFenwick = mid, dr = mid - 1;
            else
            st = mid + 1;
    }
    update(pozitieFenwick, -1);
    return pozitieFenwick;
}

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;
}