Cod sursa(job #3241666)

Utilizator SSKMFSS KMF SSKMF Data 2 septembrie 2024 08:52:45
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.24 kb
#include <fstream>
#include <random>
#include <chrono>
using namespace std;

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

mt19937 generator(chrono::steady_clock::now().time_since_epoch().count());

struct Nod {
    uint32_t prioritate;
    int valoare , cantitate;
    Nod *stanga = NULL , *dreapta = NULL;
    Nod (int __valoare = 0) { valoare = __valoare; prioritate = generator(); }
    ~Nod () { }
} *radacina , *__NULL;

inline void RotateLeft (Nod* &nod_actual)
{
    Nod *inlocuitor = nod_actual -> stanga;
    nod_actual -> stanga = inlocuitor -> dreapta;
    inlocuitor -> dreapta = nod_actual;
    
    nod_actual -> cantitate = 1 + nod_actual -> stanga -> cantitate + nod_actual -> dreapta -> cantitate;
    inlocuitor -> cantitate = 1 + inlocuitor -> stanga -> cantitate + inlocuitor -> dreapta -> cantitate;

    nod_actual = inlocuitor;
}

inline void RotateRight (Nod* &nod_actual)
{
    Nod *inlocuitor = nod_actual -> dreapta;
    nod_actual -> dreapta = inlocuitor -> stanga;
    inlocuitor -> stanga = nod_actual;

    nod_actual -> cantitate = 1 + nod_actual -> stanga -> cantitate + nod_actual -> dreapta -> cantitate;
    inlocuitor -> cantitate = 1 + inlocuitor -> stanga -> cantitate + inlocuitor -> dreapta -> cantitate;

    nod_actual = inlocuitor;
}

inline void Balance (Nod* &nod_actual)
{
    Nod *urmatorul = nod_actual;
    if (nod_actual -> stanga -> prioritate > urmatorul -> prioritate)
        { urmatorul = nod_actual -> stanga; }
    if (nod_actual -> dreapta -> prioritate > urmatorul -> prioritate)
        { urmatorul = nod_actual -> dreapta; }

    if (urmatorul == nod_actual)
        { return; }

    if (urmatorul == nod_actual -> stanga)
        { RotateLeft(nod_actual); Balance(nod_actual -> dreapta); }
    else 
        { RotateRight(nod_actual); Balance(nod_actual -> stanga); }

    nod_actual -> cantitate = 1 + nod_actual -> stanga -> cantitate + nod_actual -> dreapta -> cantitate;
}

inline Nod* Build (const int stanga , const int dreapta)
{
    if (stanga > dreapta)
        { return __NULL; }

    Nod *nod_actual = new Nod;
    const int mijloc = (stanga + dreapta) >> 1;
    nod_actual -> cantitate = dreapta - stanga + 1;
    nod_actual -> stanga = Build(stanga , mijloc - 1);
    nod_actual -> dreapta = Build(mijloc + 1 , dreapta);
    nod_actual -> valoare = mijloc;
    Balance(nod_actual);
    return nod_actual;
}

inline int Query (Nod* &nod_actual , const int pozitie)
{
    if (nod_actual -> stanga -> cantitate >= pozitie)
        { return Query(nod_actual -> stanga , pozitie); }

    if (nod_actual -> stanga -> cantitate + 1 == pozitie)
        { return nod_actual -> valoare; }

    return Query(nod_actual -> dreapta , pozitie - nod_actual -> stanga -> cantitate - 1);
}

inline void Erase (Nod* &nod_actual , const int valoare)
{
    if (nod_actual -> stanga == __NULL && nod_actual -> dreapta == __NULL)
        { delete nod_actual; nod_actual = __NULL; return; }

    if (valoare < nod_actual -> valoare)
        { Erase(nod_actual -> stanga , valoare); }
    else
        if (valoare > nod_actual -> valoare)
            { Erase(nod_actual -> dreapta , valoare); }
    else
    {
        if (nod_actual -> stanga -> prioritate > nod_actual -> dreapta -> prioritate)
            { RotateLeft(nod_actual); Erase(nod_actual -> dreapta , valoare); }
        else
            { RotateRight(nod_actual); Erase(nod_actual -> stanga , valoare); }
    }

    nod_actual -> cantitate = 1 + nod_actual -> stanga -> cantitate + nod_actual -> dreapta -> cantitate;
}

int pozitie[30001] , rezultat[30001];

int main ()
{
    int lungime;
    cin >> lungime;

    __NULL = new Nod;
    __NULL -> prioritate = 0;
    __NULL -> cantitate = 0;

    radacina = Build(1 , lungime);

    for (int indice = 1 ; indice <= lungime ; indice++)
        { cin >> pozitie[indice]; }

    for (int indice = lungime ; indice ; indice--)
    {
        const int inlocuitor = Query(radacina , pozitie[indice]);
        Erase(radacina , inlocuitor);

        rezultat[inlocuitor] = indice;
    }

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

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