Pagini recente » Cod sursa (job #2297498) | Cod sursa (job #2500643) | Cod sursa (job #1666451) | Cod sursa (job #284775) | Cod sursa (job #1275994)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
struct T{
int key, priority, s;
T *left, *right;
void update()
{
s=1;
if(left)
s+=left->s;
if(right)
s+=right->s;
}
T(int k, int p, T* l, T* r)
{
s = 0;
priority = p;
key = k;
left = l;
right = r;
}
} *R, *nil;
void init()
{
srand(time(0));
R = nil = new T(0, 0, 0, 0);
}
void rotL(T* &n)
{
T* x = n->left;
n->left = x->right;
x->right = n;
n->update();
n = x;
n->update();
}
void rotR(T* &n)
{
T* x = n->right;
n->right = x->left;
x->left = n;
n->update();
n = x;
n->update();
}
void balance(T* &n)
{
if(n->left->priority > n->priority)
rotL(n);
else if(n->right->priority > n->priority)
rotR(n);
}
void insert(T* &n, int key, int priority, float value)
{
if(n == nil)
{
n = new T(key, priority, nil, nil);
n->update();
return;
}
if(n->left->s + 1 > value)
{
insert(n->left, key, priority, value);
n->update();
}
else
{
insert(n->right, key, priority, value-(n->left->s+1));
n->update();
}
balance(n);
}
void af(T* &n)
{
if(n == nil)
return;
af(n->left);
fout << n->key << "\n";
af(n->right);
}
int main()
{
int n, i, x;
init();
fin>>n;
for(i=1; i<=n; i++)
{
fin>>x;
insert(R, i, rand()+1, x-0.5);
}
af(R);
}