Cod sursa(job #1808112)

Utilizator akaprosAna Kapros akapros Data 17 noiembrie 2016 12:48:54
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <bits/stdc++.h>

using std::pair;

struct Nod
{
    Nod* st;
    Nod* dr;
    int val;
    long long key;
    int size;
};


Nod* emptyNode;


bool isEmptyNode(Nod* rad)
{
    return rad == emptyNode;
}


void recompute(Nod* nod)
{
    nod->size = nod->st->size + 1 + nod->dr->size;
}

int getKthElement(Nod* rad, int index)
{
    assert(0 <= index && index < rad->size);
    if (rad->st->size < index)
        return getKthElement(rad->dr, index - rad->st->size - 1);
    else if (rad->st->size == index)
        return rad->val;
    else // if (index < rad->st->size)
        return getKthElement(rad->st, index);
}


pair<Nod*, Nod*> split(Nod* rad, int sizeFirst)
{
    assert(0 <= sizeFirst && sizeFirst <= rad->size);
    pair<Nod*, Nod*> answer;
    if (isEmptyNode(rad))
        answer.first = answer.second = emptyNode;
    else if (rad->st->size < sizeFirst)
    {
        pair<Nod*, Nod*> p = split(rad->dr, sizeFirst - rad->st->size - 1);
        answer.first = rad;
        rad->dr = p.first;
        answer.second = p.second;
        recompute(rad);
    }
    else // if (sizeFirst <= rad->st->size)
    {
        pair<Nod*, Nod*> p = split(rad->st, sizeFirst);
        answer.second = rad;
        rad->st = p.second;
        answer.first = p.first;
        recompute(rad);
    }


    return answer;
}


Nod* join(Nod* first, Nod* second)
{
    if (isEmptyNode(first))
        return second;
    if (isEmptyNode(second))
        return first;
    if (second->key > first->key)
    {
        second->st = join(first, second->st);
        recompute(second);
        return second;
    }
    else   // second->key <= first->key
    {
        first->dr = join(first->dr, second);
        recompute(first);
        return first;
    }
}


Nod* insert(Nod* rad, int index, int val)
{
    assert(0 <= index && index <= rad->size);
    Nod* nodNou = new Nod();
    nodNou->val = val;
    nodNou->st = nodNou->dr = emptyNode;
    nodNou->key =((long long)rand() << 45
                  ^ (long long)rand() << 30
                  ^ (long long)rand() << 15
                  ^ (long long)rand() <<  0)
                 & 0x7fffffffffffffff;
    nodNou->size = 1;
   // nodNou->sum = nodNou->val;
    pair<Nod*, Nod*> p = split(rad, index);
    return join(join(p.first, nodNou), p.second);
}


void deleteAll(Nod* rad)
{
    if (rad != emptyNode)
    {
        deleteAll(rad->st);
        deleteAll(rad->dr);
        delete rad;
    }
}

Nod* eraseAll(Nod* rad, int x1, int x2)
{
    assert(0 <= x1 && x1 < x2 && x2 <= rad->size);
    pair<Nod*, Nod*> p = split(rad, x2);
    pair<Nod*, Nod*> q = split(p.first, x1);
    deleteAll(q.second);
    return join(q.first, p.second);
}
int main()
{
    int n;
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    emptyNode = new Nod();
    emptyNode->val = 0;
    emptyNode->key = -1;
    emptyNode->st = emptyNode;
    emptyNode->dr = emptyNode;
    emptyNode->size = 0;
    //emptyNode->sum = 0;

    scanf("%d", &n);

    Nod* rad = emptyNode;
    for (int i = 1; i <= n; ++ i)
        rad = insert(rad, i - 1, i);

    int p = 1;
    for (int i = 1; i <= n; ++ i)
    {
        p = (p + i - 1) % (n - i + 1);
        printf("%d ", getKthElement(rad, p));
        rad = eraseAll(rad, p, p + 1);
    }
    printf("\n");
    return 0;
}