Cod sursa(job #1524253)

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

const int BSIZE = 65536;

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

Treap *Root, *NIL;

char buffer[BSIZE];
int ptr = 0;

inline void putChr(const char &C) {
    buffer[ptr++] = C;
    if (ptr == BSIZE) {
        fwrite(buffer, 1, BSIZE, stdout);
        ptr = 0;
    }
}

inline void writeInt(int Q) {
    char digs[10];
    int q, n = 0;
    do {
        q = Q / 10;
        digs[n++] = Q - q * 10 + '0';
        Q = q;
    } while (Q);
    while (n--) {
        putChr(digs[n]);
    }
}

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 = new Treap(key, priority, 1, NIL, 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);
    }
}

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 (register int i = 1; i <= n; i++) {
        treapInsert(Root, i, i, (rand() << 15) ^ rand());
    }

    pos = 2;
    for (register int i = 0; i < n; i++) {
        pos = (pos + i) % (n - i);
        pos += ((n - i) & -(pos == 0));
        writeInt(treapGet(Root, pos));
        putChr(' ');
        treapErase(Root, pos);
    }
    fwrite(buffer, 1, ptr, stdout);
    fclose(stdout);
    return 0;
}