Cod sursa(job #2751854)

Utilizator Pop_MariaPop Maria Pop_Maria Data 15 mai 2021 22:54:40
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>

using namespace std;

int v[30005];
int w[3*30005];
int pozitie, x, y;

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

    int mijloc = (stanga + dreapta) / 2;

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

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

    int mijloc = (stanga + dreapta) / 2;

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

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

int numar_de_concurenti, clasament[30002];

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

    fin >> numar_de_concurenti;

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

    for(int i = numar_de_concurenti; i >= 1; i--)
    {
        x = v[i];
        y = 0;

        query(1, 1, numar_de_concurenti);

        pozitie = y;
        clasament[y] = i;
        x = 0;

        actualizare(1, 1, numar_de_concurenti);
    }

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

    return 0;

}