Cod sursa(job #1812896)

Utilizator mirupetPetcan Miruna mirupet Data 22 noiembrie 2016 15:35:21
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 kb
#include<cstdio>
#include<utility>
#include<cstdlib>
using namespace std;


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


int N, r;


struct Node
{
    Node* left;
    Node* right;
    int val;
    int counter; // size
    long long priority;
};


Node* emptyNode;


pair < Node*, Node* > split(Node* node, int k)
{
    pair < Node*, Node* > p;
    if (node == emptyNode)
    {
        p.first = emptyNode;
        p.second = emptyNode;
    }
    else
    {
        if (node -> left -> counter < k)
        {
            pair < Node*, Node* > q = split(node -> right, k - node -> left -> counter - 1);
            p.first = node;
            node -> right = q.first;
            p.second = q.second;
            node -> counter = node -> left -> counter + node -> right -> counter + 1;
        }
        else
        {
            pair < Node*, Node* > q = split(node -> left, k);
            p.second = node;
            node -> left = q.second;
            p.first = q.first;
            node -> counter = node -> left -> counter + node -> right -> counter + 1;
        }
    }
    return p;
}


Node* join(Node* first, Node* second)
{
    if (first == emptyNode)
        return second;
    if (second == emptyNode)
        return first;


    if (first -> priority < second -> priority)
    {
        second -> left = join(second -> left, first);
        second -> counter = second -> left -> counter + second -> right -> counter+ 1;
        return second;
    }
    else
    {
        first -> right = join(first -> right, second);
        first -> counter = first -> right -> counter + first -> left -> counter + 1;
        return first;
    }
}


Node* Insert(Node* node, int val, int ind)
{
    Node* newNode = new Node();
    newNode -> val = val;
    newNode -> counter = 1;
    newNode -> left = newNode -> right = emptyNode;
    newNode -> priority = ((long long)rand() << 45)
                        ^ ((long long)rand() << 30)
                        ^ ((long long)rand() << 15)
                        ^ ((long long)rand() <<  0);
    newNode -> priority &= 0x7fffffffffffffff; // se sterge bitul de semn (devine 0)
    pair < Node*, Node* > p = split(node, ind);
    p.first = join(p.first, newNode);
    return join(p.first, p.second);
}


int kth_element(Node* &node, int k)
{
    int sol;
    if (node -> left -> counter < k)
    {
        sol = kth_element(node -> right, k - node -> left -> counter - 1);
        node -> counter = node -> right -> counter + node -> left -> counter + 1;
    }
    else
        if (node -> left -> counter == k)
        {
            sol = node -> val;
            node = join(node -> left, node -> right);
        }
    else
        {
            sol = kth_element(node -> left, k);
            node -> counter = node -> left -> counter + node -> right -> counter + 1;
        }


    return sol;
}



int main()
    {
        scanf("%d", &N);
        emptyNode = new Node();
        emptyNode -> left = emptyNode;
        emptyNode -> right = emptyNode;
        emptyNode -> val = 0;
        emptyNode -> priority = -1;
        emptyNode -> counter = 0;


        Node* root = emptyNode;


        for (int i = 1; i <= N; i++) {
            root = Insert(root, i, i - 1);
        }
        r = 1;
        for (int i = 1; i <= N; i++)
        {
            r = (r + i - 1) % (N - i + 1);
            printf("%d ", kth_element(root, r));
        }
        return 0;
    }