Cod sursa(job #1812860)

Utilizator mirupetPetcan Miruna mirupet Data 22 noiembrie 2016 14:49:44
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.52 kb
#include<cstdio>
#include<utility>
#include<cassert>
#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;
    long long priority;
};

Node* emptyNode;

pair < Node*, Node* > split(Node* node, int k)
{
    //assert(0 <= k && k <= node -> counter);
    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 + first -> counter + 1;
        return second;
    }
    else
    {
        first -> right = join(first -> right, second);
        first -> counter = first -> right -> counter + second -> counter + 1;
        return first;
    }
}

Node* Insert(Node* node, int val, int ind)
{
    //assert(0 <= ind && ind <= node -> counter);
    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);
    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 = 0;
    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 = NULL;
        emptyNode -> right = NULL;
        emptyNode -> val = 0;
        emptyNode -> priority = -1;
        emptyNode -> counter = 0;

        Node* root = emptyNode;

        //root = Insert(root, 1, 0);
        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));
        }
    }