Pagini recente » Cod sursa (job #2122772) | Cod sursa (job #2564022) | Cod sursa (job #2035199) | Cod sursa (job #2690207) | Cod sursa (job #1668535)
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
struct treap{
int ind, s;
int priority;
treap *l, *r;
treap(int i, int p, treap *le, treap *ri)
{
ind = i;
priority = p;
l = le;
r = ri;
s = 0;
}
} *R, *nil;
void init()
{
R = nil = new treap(0, 0, 0, 0);
}
void update(treap *&R)
{
R->s = R->l->s + R->r->s + 1;
}
void Rleft(treap* &R)
{
treap *p = R->l;
R->l = p->r;
p->r = R;
update(R);
R = p;
update(R);
}
void Rright(treap* &R)
{
treap *p = R->r;
R->r = p->l;
p->l = R;
update(R);
R = p;
update(R);
}
void balance(treap* &R)
{
if(R->l->priority > R->priority)
Rleft(R);
else if(R->r->priority > R->priority)
Rright(R);
}
void insereaza(treap *&R, double x, int i)
{
if(R == nil)
{
R = new treap(i, rand() + 1, nil, nil);
update(R);
return;
}
if(1.0 * R->l->s + 1 > x)
{
insereaza(R->l, x, i);
}
else
{
insereaza(R->r, x - R->l->s - 1, i);
}
update(R);
balance(R);
}
void df(treap *R)
{
if(R == nil)
return;
df(R->l);
fout << R->ind << "\n";
df(R->r);
}
int main()
{
int n, i, x;
init();
fin >> n;
for(i = 1 ; i <= n ; i++)
{
fin >> x;
insereaza(R, 1.0 * x - 0.5, i);
}
df(R);
}