Pagini recente » Cod sursa (job #940925) | Cod sursa (job #731351) | Cod sursa (job #2738305) | Cod sursa (job #2830759) | Cod sursa (job #3241652)
#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;
}