Cod sursa(job #3295744)

Utilizator rapidu36Victor Manz rapidu36 Data 8 mai 2025 09:28:02
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <vector>

using namespace std;

int caut_liber(int loc, vector <int> &aib)
{
    int p2 = 1, n = (int)aib.size() - 1, poz = 0;
    while (p2 * 2 <= n)
    {
        p2 *= 2;
    }
    while (p2 != 0)
    {
        int poz_c = poz + p2;
        int lung = poz_c & (-poz_c);
        if (poz_c <= n && lung - aib[poz_c] < loc)
        {
            loc -= lung - aib[poz_c];
            poz = poz_c;
        }
        p2 /= 2;
    }
    return poz + 1;
}

void actualizare(int p, vector <int> &aib)
{
    int n = (int)aib.size() - 1;
    while (p <= n)
    {
        aib[p] += 1;
        int p2 = p & (-p);
        p += p2;
    }
}

int main()
{
    ifstream in("schi.in");
    ofstream out("schi.out");
    int n;
    in >> n;
    vector <int> clas_ini(n + 1);
    for (int i = 1; i <= n; i++)
    {
        in >> clas_ini[i];
    }
    vector <int> aib(n + 1, 0), clas_fin(n + 1);
    for (int i = n; i >= 1; i--)
    {
        int poz = caut_liber(clas_ini[i], aib);
        clas_fin[poz] = i;
        actualizare(poz, aib);
    }
    for (int i = 1; i <= n; i++)
    {
        out << clas_fin[i] << "\n";
    }
    in.close();
    out.close();
    return 0;
}