Cod sursa(job #1524232)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 13 noiembrie 2015 18:26:00
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.62 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>

const int BSIZE = 2048;

struct Treap {
    int key, priority;
    int siz;
    Treap *left, *right;
    Treap() {
    }
    Treap (int k, int p, int s, Treap* l, Treap* r) : key(k), priority(p), siz(s), left(l), right(r) {
    }
};

Treap *Root, *NIL;

inline Treap *alloc() {
    static Treap *ptr;
    static int pos = BSIZE;
    if (pos == BSIZE) {
        ptr = new Treap[BSIZE];
        pos = 0;
    }
    return &ptr[pos++];
}

inline void persistent(Treap* &node) {
    if (node != NIL) {
        node->siz = node->left->siz + node->right->siz + 1;
    }
}

inline void updateNode(Treap* &node) {
    persistent(node->left);
    persistent(node->right);
    persistent(node);
}

void rotLeft(Treap* &node) {
    Treap* T = node->left;
    node->left = T->right;
    T->right = node;
    updateNode(node);
    node = T;
    updateNode(node);
}

void rotRight(Treap* &node) {
    Treap* T = node->right;
    node->right = T->left;
    T->left = node;
    updateNode(node);
    node = T;
    updateNode(node);
}

void balance(Treap* &node) {
    updateNode(node);
    if (node->left->priority > node->priority) {
        rotLeft(node);
    } else if (node->right->priority > node->priority) {
        rotRight(node);
    }
    updateNode(node);
}

void treapInsert(Treap* &node, int pos, int key, int priority) {
    if (node == NIL) {
        node = alloc();
        node->key = key;
        node->priority = priority;
        node->left = NIL; node->right = NIL;
        return;
    }
    updateNode(node);
    if (pos <= node->left->siz) {
        treapInsert(node->left, pos, key, priority);
    } else {
        treapInsert(node->right, pos - node->left->siz - 1, key, priority);
    }
    balance(node);
}

void treapErase(Treap* &node, int pos) {
    if (node == NIL) {
        return ;
    }
    updateNode(node);
    if (pos <= node->left->siz) {
        treapErase(node->left, pos);
    } else if (pos > node->left->siz + 1) {
        treapErase(node->right, pos - node->left->siz - 1);
    } else {
        if (node->left == NIL && node->right == NIL) {
            delete node;
            node = NIL;
        } else {
            if (node->left->priority > node->right->priority) {
                rotLeft(node);
                treapErase(node->right, pos - node->left->siz - 1);
            } else {
                rotRight(node);
                treapErase(node->left, pos);
            }
        }
    }
    if (node != NIL) {
        updateNode(node);
    }
}

int treapGet(Treap* &node, int pos) {
    updateNode(node);
    if (pos == node->left->siz + 1) {
        return node->key;
    } else if (pos <= node->left->siz) {
        return treapGet(node->left, pos);
    } else {
        return treapGet(node->right, pos - node->left->siz - 1);
    }
}

void dump(Treap* &node) {
    if (node == NIL) {
        return;
    }
    updateNode(node);
    dump(node->left);
    printf("%d ", 1 + node->key);
    dump(node->right);
}

int main(void) {
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    int n, pos;

    scanf("%d", &n);
    fclose(stdin);

    Root = NIL = new Treap(0, 0, 0, NULL, NULL);

    srand(time(0));
    for (int i = 1; i <= n; i++) {
        treapInsert(Root, i, i, rand());
    }

    pos = 2;
    for (int i = 0; i < n; i++) {
        pos = (pos + i) % (n - i);
        pos += ((n - i) & -(pos == 0));
        printf("%d ", treapGet(Root, pos));
        treapErase(Root, pos);
    }
    fclose(stdout);
    return 0;
}