Pagini recente » Monitorul de evaluare | Profil alexradu04 | Clasament dupa rating | Rating Andra Maierean (andra.maierean) | Cod sursa (job #3241666)
#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;
}