Pagini recente » Istoria paginii runda/prep/clasament | Cod sursa (job #2184920) | Cod sursa (job #497756) | Monitorul de evaluare | Cod sursa (job #1291212)
#include<fstream>
#include<cstdlib>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
struct treap {
int d, poz, pr;
treap *f1, *f2;
treap() {}
treap(int _poz, int _pr, int _d, treap *_f1, treap *_f2) {
poz = _poz;
pr = _pr;
d = _d;
f1 = _f1;
f2 = _f2;
}
};
treap *nil = new treap(0, 0, 0, NULL, NULL);
treap *R;
void rotLeft(treap * &n) {
treap *temp = n->f1;
n->f1 = temp->f2;
temp->f2 = n;
n = temp;
}
void rotRight(treap* &n) {
treap *temp = n->f2;
n->f2 = temp->f1;
temp->f1 = n;
n = temp;
}
void recalc(treap * &n) {
if(n != nil) {
n->d = 1 + n->f1->d + n->f2->d;
}
}
void balance(treap* &n) {
if(n->f2->pr > n->pr)
rotRight(n);
if(n->f1->pr > n->pr)
rotLeft(n);
recalc(n->f1);
recalc(n->f2);
recalc(n);
}
void insert(treap* &n, int key, int val) {
if(n == nil) {
n = new treap(key, rand() + 1, 1, nil, nil);
return;
}
if(n->f1->d < val) {
insert(n->f2, key, val - (n->f1->d) - 1);
}
else {
insert(n->f1, key, val);
}
balance(n);
}
void print(treap* &n) {
if(n == nil) {
return;
}
print(n->f1);
fout << n->poz << "\n";
print(n->f2);
}
int main() {
int n, x;
srand(666);
fin >> n;
fin >> x;
R = new treap(1, rand() + 1, 1, nil, nil);
for(int i = 2; i <= n; ++i) {
int x;
fin >> x;
insert(R, i, x - 1);
}
print(R);
return 0;
}