Cod sursa(job #1291206)

Utilizator assa98Andrei Stanciu assa98 Data 12 decembrie 2014 15:27:30
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<fstream>
#include<ctime>
#include<cstdlib>
using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

const int N = 30100;
 
struct treap {
    short 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;
    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;
}