Cod sursa(job #225331)

Utilizator JohnnyBravoJohnny Bravo JohnnyBravo Data 30 noiembrie 2008 16:18:26
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.58 kb
#include <fstream>
using namespace std;

ifstream in("order.in");
ofstream out("order.out");

class Treap {
private:
    struct Node {
        short int value, count;
        int probability;
        Node *left, *right;
        Node(int _value) {
            value = _value;
            count = 1;
            probability = rand() % 1000000007;
            left = right = NULL;
        }
    };

    Node *root;

    int repair_count(Node *p) {
        return 1 + (p->left != NULL ? p->left->count : 0) + (p->right != NULL ? p->right->count : 0);
    }
    void rotleft(Node *&);
    void rotright(Node *&);
    void insert(Node*&, Node*&);
    void remove(Node*&, int);
    int find(Node*, int);

public:
    Treap(): root(NULL) {
        srand(time(0));
    }
    void insert(int value) {
        Node *p = new Node(value);
        insert(root, p);
    }
    void remove(int value) {
        remove(root, value);
    }
    int find(int pos) {
        return find(root, pos);
    }
};

void Treap::rotleft(Node *&root) {
    Node *p = root->right;
    root->right = p->left;
    p->left = root;
    root->count = repair_count(root);
    p->count = repair_count(p);
    root = p;
}

void Treap::rotright(Node *&root) {
    Node *p = root->left;
    root->left = p->right;
    p->right = root;
    root->count = repair_count(root);
    p->count = repair_count(p);
    root = p;
}

void Treap::insert(Node *&root, Node *&p) {
    if(root == NULL) {
        root = p;
        return;
    }
    if(p->value < root->value) {
        if(root->left == NULL)
            root->left = p;
        else
            insert(root->left, p);
        root->count = repair_count(root);
        if(root->probability < root->left->probability)
            rotright(root);
    }
    else {
        if(root->right == NULL)
            root->right = p;
        else
            insert(root->right, p);
        root->count = repair_count(root);
        if(root->probability < root->right->probability)
            rotleft(root);
    }
}

void Treap::remove(Node *&root, int value) {
    if(root == NULL)
        return;
    if(value < root->value) {
        remove(root->left, value);
        root->count = repair_count(root);
        return;
    }
    if(value > root->value) {
        remove(root->right, value);
        root->count = repair_count(root);
        return;
    }

    if(!root->left && !root->right) {
        root = NULL;
        return;
    }

    if(!root->left || (root->right && root->right->probability > root->left->probability)) {
        rotleft(root);
        remove(root->left, value);
        root->count = repair_count(root);
        return;
    }

    if(!root->right || (root->left && root->left->probability > root->right->probability)) {
        rotright(root);
        remove(root->right, value);
        root->count = repair_count(root);
        return;
    }
}

int Treap::find(Node *root, int pos) {
    int cnt = root->left == NULL ? 0 : root->left->count;
    if(pos <= cnt)
        return find(root->left, pos);
    if(pos == cnt + 1)
        return root->value;
    return find(root->right, pos - cnt - 1);
}


int main() {
    int N;
    in >> N;

    Treap T;
    for(int i = 1; i <= N; ++i)
        T.insert(i);

    for(int step = 1, pos = 1, value; step <= N; ++step) {
        pos = (pos + step - 1) % (N - step + 1) + 1;
        out << (value = T.find(pos)) << " ";
        T.remove(value);
        --pos;
        if(!pos)
            pos = (N - step + 1) - 1;
    }

    return 0;
}