Cod sursa(job #2751849)

Utilizator Pop_MariaPop Maria Pop_Maria Data 15 mai 2021 22:27:53
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>

using namespace std;

int v[30005];
int w[3*30005];

void actualizare(int nod, int stanga, int dreapta, int pozitie)
{
    if(stanga == dreapta)
    {
        w[nod] = 0;
        return;
    }

    int mijloc = (stanga + dreapta) / 2;

    if(mijloc < pozitie)
    {
        actualizare(2 * nod + 1, mijloc + 1, dreapta, pozitie);
    }
    else
    {
        actualizare(2 * nod, stanga, mijloc, pozitie);
    }

    w[nod] = w[2 * nod] + w[2 * nod + 1];
}

int query(int nod, int stanga, int dreapta, int a)
{
    if(stanga == dreapta)
    {
        return stanga;
    }

    int mijloc = (stanga + dreapta) / 2;

    if(w[2 * nod] < a)
    {
        return query(2 * nod + 1, mijloc + 1, dreapta, a - w[2 * nod]);
    }
    else
    {
        return query(2 * nod, stanga, mijloc, a);
    }
}

void construire(int nod, int stanga, int dreapta)
{
    if(stanga == dreapta)
    {
        w[nod] = 1;
        return;
    }

    int mijloc = (stanga + dreapta) / 2;
    construire(2 * nod + 1, mijloc + 1, dreapta);
    construire(2 * nod, stanga, mijloc);

    w[nod] = w[2 * nod + 1] + w[2 * nod] ;
}

int pozitie, numar_de_concurenti, clasament[30005];

int main()
{
    ifstream fin("date.in");
    ofstream fout("date.out");

    fin >> numar_de_concurenti;

    construire(1, 1, numar_de_concurenti);

    for(int i = 1; i <= numar_de_concurenti; i++)
    {
        fin >> v[i];
    }

    for(int i = numar_de_concurenti; i > 0; i--)
    {
        pozitie = query(1, 1, numar_de_concurenti, v[i]);
        clasament[pozitie] = i;
        actualizare(1, 1, numar_de_concurenti, pozitie);
    }

    for(int i = 1; i <= numar_de_concurenti; i++)
    {
        fout << clasament[i] << '\n';
    }

    return 0;

}