Cod sursa(job #3241652)

Utilizator SSKMFSS KMF SSKMF Data 1 septembrie 2024 19:01:48
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.52 kb
#include <fstream>
#include <random>
#include <chrono>
using namespace std;

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

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

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

inline int size (Nod *nod_actual) { return nod_actual ? nod_actual -> cantitate : 0; }

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

    if (candidat != nod_actual) {
        swap(nod_actual -> prioritate , candidat -> prioritate);
        Heapify(candidat);
    }
}

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 -> valoare = mijloc;

    nod_actual -> stanga = Build(stanga , mijloc - 1);
    nod_actual -> dreapta = Build(mijloc + 1 , dreapta);
    nod_actual -> cantitate = 1 + size(nod_actual -> stanga) + size(nod_actual -> dreapta);
    Heapify(nod_actual);
    return nod_actual;
}

inline int Query_1 (Nod *nod_actual , const int limita)
{
    if (!nod_actual)
        { return 0; }

    if (limita < nod_actual -> valoare)
        { return Query_1(nod_actual -> stanga , limita); }

    return size(nod_actual -> stanga) + 1 + Query_1(nod_actual -> dreapta , limita);
}

inline int Query_2 (Nod *nod_actual , const int pozitie)
{
    if (size(nod_actual -> stanga) + 1 == pozitie)
        { return nod_actual -> valoare; }

    if (pozitie <= size(nod_actual -> stanga))
        { return Query_2(nod_actual -> stanga , pozitie); }

    return Query_2(nod_actual -> dreapta , pozitie - size(nod_actual -> stanga) - 1);
}

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

    nod_actual -> cantitate = 1 + size(nod_actual -> stanga) + size(nod_actual -> dreapta);
    inlocuitor -> cantitate = 1 + size(inlocuitor -> stanga) + size(inlocuitor -> dreapta);

    nod_actual = inlocuitor;
}

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

    nod_actual = inlocuitor;
}

inline void Erase (Nod* &nod_actual , const int valoare)
{
    if (!nod_actual -> stanga && !nod_actual -> dreapta)
        { 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)
            { RotateLeft(nod_actual); Erase(nod_actual , valoare); }
        else
            if (!nod_actual -> dreapta)
                { RotateRight(nod_actual); Erase(nod_actual , valoare); }
        else
            if (nod_actual -> stanga -> prioritate > nod_actual -> dreapta -> prioritate)
                { RotateRight(nod_actual); Erase(nod_actual , valoare); }
        else 
            { RotateLeft(nod_actual); Erase(nod_actual , valoare); }
    }

    nod_actual -> cantitate = 1 + size(nod_actual -> stanga) + size(nod_actual -> dreapta);
}

int main ()
{
    int lungime;
    cin >> lungime;
    
    radacina = Build(1 , lungime);
    for (int indice = 1 , actual = 1 ; indice <= lungime ; indice++)
    {
        int termen = (indice - 1) % (lungime - indice + 1) + 1;
        const int ramas = lungime - indice + 1 - Query_1(radacina , actual);
        if (ramas < termen) { termen -= ramas; }
        else { termen += lungime - indice + 1 - ramas; }
    
        actual = Query_2(radacina , termen);
        cout << actual << ' ';

        Erase(radacina , actual);
    }
    
    cout.close(); cin.close();
    return 0;
}