Cod sursa(job #3140556)

Utilizator SSKMFSS KMF SSKMF Data 7 iulie 2023 09:15:38
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
using namespace std;

ifstream cin ("schi.in");
ofstream cout ("schi.out");

int lungime , sir[30001] , clasament[30001] , aparitii[30001];

void Update (int indice)
{
    while (indice <= lungime) {
        aparitii[indice]++;
        indice += (indice & -indice);
    }
}

int Suma (int indice)
{
    int suma = 0;
    while (indice) {
        suma += aparitii[indice];
        indice -= (indice & -indice);
    }

    return suma;
}

int CautareBinara (int libere)
{
    int stanga = libere + 1 , dreapta = lungime , pozitie = stanga;
    while (stanga <= dreapta) 
    {
        int mijloc = (stanga + dreapta) / 2 , ramase = mijloc - Suma(mijloc - 1) - 1;
        if (ramase == libere)
        {
            if (!clasament[mijloc])
                pozitie = mijloc , dreapta = stanga - 1;
            else
                stanga = mijloc + 1;
        }
        else 
            if (ramase > libere)
                dreapta = mijloc - 1;
        else
            stanga = mijloc + 1;
    }

    return pozitie;
}

int main ()
{
    cin >> lungime;

    for (int indice = 1 ; indice <= lungime ; indice++)
        cin >> sir[indice];

    for (int indice = lungime ; indice ; indice--)
    {
        int pozitie = CautareBinara(sir[indice] - 1);
        clasament[pozitie] = indice;
        Update(pozitie);
    }

    for (int indice = 1 ; indice <= lungime ; indice++)
        cout << clasament[indice] << '\n';

    cout.close(); cin.close();
    return 0;
}