Cod sursa(job #1478143)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 28 august 2015 00:16:47
Problema Order Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.22 kb
/**
  *  Worg
  */
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;
FILE *fin=freopen("order.in","r",stdin);
FILE *fout=freopen("order.out","w",stdout);

struct treap {

        int key, priority, total, maxim;
        treap *left, *right;

        treap(int key, int priority, int total, treap *left, treap *right) {

            this->key = key, this->priority = priority, this->total = total, this->maxim = key;
            this->left = left, this->right = right;
        }
} *root, *empty;

void update(treap *node) {

    if(node == empty)
        node->total = node->maxim = 0;
    else
        node->total = node->left->total + node->right->total + 1,
        node->maxim = max(max(node->left->maxim, node->right->maxim), node->key);
}

void rotLeft(treap *&node) {

    treap *T = node->left;
    node->left = T->right, T->right = node;
    node = T;

    update(node->right); update(node);
}

void rotRight(treap *&node) {

    treap *T = node->right;
    node->right = T->left, T->left = node;
    node = T;

    update(node->left); update(node);
}

void balance(treap *&node) {

    if(node->priority < node->left->priority)
        rotLeft(node);
    else if(node->priority < node->right->priority)
        rotRight(node);
}

void insert(treap *&node, int key) {

    if(node == empty) {

        node = new treap(key, rand() + 1, 1, empty, empty);
        return;
    }
    if(key < node->key)
        insert(node->left, key);
    else
        insert(node->right, key);

    update(node);
    balance(node);
}

void erase(treap *&node, int key) {

    if(node == empty)
        return;
    if(key < node->key)
        erase(node->left, key);
    else if(key > node->key)
        erase(node->right, key);
    else {

        if(node->left == empty && node->right == empty)
            delete node, node = empty;
        else {
            if(node->left->priority > node->right->priority){
                rotLeft(node);
                erase(node->right, key);
            }
            else {
                rotRight(node);
                erase(node->left, key);
            }
        }
    }
    update(node);
}

int smaller_than(treap *node, int key) {

    if(node == empty)
        return 0;
    if(key > node->key)
        return node->left->total + 1 + smaller_than(node->right, key);
    if(key == node->key)
        return node->left->total + 1;
    return smaller_than(node->left, key);
}

int bigger_than(treap *node, int key) {

    if(node == empty)
        return 0;
    if(key < node->key)
        return node->right->total + 1 + bigger_than(node->left, key);
    if(key == node->key)
        return node->right->total + 1;
    return bigger_than(node->right, key);
}

int next_element(treap *node, int key) {

    if(node == empty)
        return -1;

    if(key < node->key && key < node->left->maxim)
        return next_element(node->left, key);
    if(key < node->key)
        return node->key;
    return next_element(node->right, key);
}


void write(treap *node) {

    if(node == empty)
        return;

    write(node->left);
    printf("%d ", node->key);
    write(node->right);
}

void init() {

    srand(unsigned(time(0)));
    root = empty = new treap(0, 0, 0, NULL, NULL);
}

int main() {

    init();
    int n, pos = 1, k, rest, left, right, mid, sol, q;

    scanf("%d", &n); rest = n;

    for(int i = 1; i <= n; ++i)
        insert(root, i);

    for(int i = 1; i <= n; ++i, --rest) {

        k = i % rest - 1, pos = next_element(root, pos);
        if(k == -1)
            k = rest - 1;
        if(pos == -1)
            pos = next_element(root, 0);
        q = bigger_than(root, pos);
        if(q <= k)
            pos = next_element(root, 0), k -= q;


        left = sol = pos, right = n;
        while(left <= right) {

            mid = (left + right) >> 1;
            if(k <= smaller_than(root, mid) - smaller_than(root, pos))
                sol = mid, right = mid - 1;
            else
                left = mid + 1;
        }

        erase(root, sol);
        printf("%d ", sol);
        pos = sol;
    }

    return 0;
}