Cod sursa(job #1291207)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 12 decembrie 2014 15:29:52
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<cstdio>
#include<time.h>
#include<cstdlib>
using namespace std;
 
const int N = 30100;
 
struct t {
    short k, nrel;
    short p;
    t *f1, *f2;
 
    t() {
        k = p = 0;
        nrel = 0;
    }
 
    t(short a, short b, t *c, t *d) {
        k = a; p = b;
        f1 = c; f2 = d;
        nrel = 1;
    }
};
 
t *rad, *nil;
 
int n;
 
void rotLeft(t* &r) {
    t *temp = r->f1;
    r->f1 = temp->f2;
    temp->f2 = r;
    r = temp;
}
 
void rotRight(t* &r) {
    t *temp = r->f2;
    r->f2 = temp->f1;
    temp->f1 = r;
    r = temp;
}
 
void recalc(t* &r) {
    if(r != nil)
        r->nrel = 1 + r->f1->nrel + r->f2->nrel;
}
 
void balance(t* &r) {
    if(r->f2->p > r->p)
        rotRight(r);
    if(r->f1->p > r->p)
        rotLeft(r);
 
    recalc(r->f1);
    recalc(r->f2);
    recalc(r);
}
 
void update(t* &r, short key, short val, short pri) {
    if(r == nil) {
        r = new t(key, pri, nil, nil);
        return;
    }
 
    if(r->f1->nrel < val)
        update(r->f2, key, val - (r->f1->nrel) - 1, pri);
    else
        update(r->f1, key, val, pri);
 
    balance(r);
}
 
void print(t* &r) {
    if(r == nil)
        return;
    print(r->f1);
    printf("%d\n", r->k);
    print(r->f2);
}
 
int main() {
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    int i;
 
    srand(777);
    nil = new t;
    rad = new t;
    nil->f1 = nil->f2 = nil;
short x;
    scanf("%d", &n);
    scanf("%d", &x);
    rad->k = 1;
    rad->p = rand() % 32000 + 1;
    rad->f1 = rad->f2 = nil;
    rad->nrel = 1;
 
    for(i = 2; i <= n; ++i) {
            short x;
        scanf("%d", &x);
        update(rad, i, x - 1, rand()%32000 + 1);
    }
 
    print(rad);
 
    return 0;
}