Cod sursa(job #1955367)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 5 aprilie 2017 22:16:16
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <bits/stdc++.h>

using namespace std;

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

int i, n, k, ans;

int MyRand()
{
    int x = rand();
    return max(x, -x) + 5;
}

struct Treap
{
    int key, prio, cnt;
    Treap *left, *right;

    Treap(int _key, int _prio, int _cnt, Treap *_left, Treap *_right)
    {
        key = _key, prio = _prio, cnt = _cnt, left = _left, right = _right;
    }
} *root, *nul;

void rotate_left(Treap *& b)
{
    Treap *a = b->left;
    b->left = a->right;
    a->right = b;
    b = a;

    int s = 0;
    if(b->right->left) s += b->right->left->cnt;
    if(b->right->right) s += b->right->right->cnt;

    b->right->cnt = s + 1;

    s = 0;
    if(b->left) s += b->left->cnt;
    if(b->right) s += b->right->cnt;
    b->cnt = s + 1;
}

void rotate_right(Treap *& b)
{
    Treap *a = b->right;
    b->right = a->left;
    a->left = b;
    b = a;

    int s = 0;
    if(b->left->left) s += b->left->left->cnt;
    if(b->left->right) s += b->left->right->cnt;

    b->left->cnt = s + 1;

    s = 0;
    if(b->left) s += b->left->cnt;
    if(b->right) s += b->right->cnt;
    b->cnt = s + 1;
}

void balance(Treap *& t)
{
    if(t->left->prio > t->prio) rotate_left(t);
    else if(t->right->prio > t->prio) rotate_right(t);
}

int query(Treap *t, int k)
{
    if(t->left->cnt == k-1) return t->key;

    if(t->left->cnt >= k) return query(t->left, k);
    return query(t->right, k - t->left->cnt - 1);
}

void add(Treap *&t, int Key)
{
    if(t == nul)
    {
        t = new Treap(Key, MyRand(), 1, nul, nul);
        return;
    }

    if(Key <= t->key) add(t->left, Key);
    else add(t->right, Key);

    balance(t);
    t->cnt = t->left->cnt + t->right->cnt + 1;
}

void del(Treap *&t, int Key)
{
    if(t->key == Key)
    {
        if(t->left == nul && t->right == nul)
        {
            delete t;
            t = nul;
            return;
        }

        if(t->left->prio > t->right->prio)
        {
            rotate_left(t);
            del(t->right, Key);
        }
        else
        {
            rotate_right(t);
            del(t->left, Key);
        }
    }
    else if(Key <= t->key) del(t->left, Key);
        else del(t->right, Key);

    t->cnt = t->left->cnt + t->right->cnt + 1;
}

int main()
{
    srand(time(0));
    nul = new Treap(0, 0, 0, NULL, NULL);
    root = new Treap(0, 1, 1, nul, nul);

    fin >> n;
    for(i=1; i<=n; ++i)
        add(root, i);

    k = 2;
    for(i=0; i<n; ++i)
    {
        k += i;
        k %= (n-i);
        if(!k) k = n-i;

        ans = query(root, k+1);
        fout << ans << ' ';

        del(root, ans);
    }

    return 0;
}