Cod sursa(job #222326)

Utilizator MariusMarius Stroe Marius Data 21 noiembrie 2008 20:49:44
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const char iname[] = "order.in";
const char oname[] = "order.out";

#define getc(n)  ((n)->cnt = (n)->left->cnt + (n)->right->cnt + 1)

struct T {
    int key, cnt, priority;
    T *left, *right;
} *R, *nil;


void init(T* &R)
{
    srand((unsigned)time(0));

    R = nil = new T();
    nil->key = nil->cnt = nil->priority = 0,
            nil->left = nil->right = NULL;
}

void rotleft(T* &n)
{
    T *t = n->left;
    n->left = t->right, t->right = n,
                getc(n), getc(t);
    n = t;
}

void rotright(T* &n)
{
    T *t = n->right;
    n->right = t->left, t->left = n,
                getc(n), getc(t);
    n = t;
}

void balance(T* &n)
{
    if (n->left->priority > n->priority)
        rotleft(n);
    else if (n->right->priority > n->priority)
        rotright(n);
}

void insert(T* &n, int key)
{
    if (n == nil)
    {
        n = new T();
        n->key = key, n->cnt = 1, n->priority = rand() + 1,
                n->left = n->right = nil;
        return ;
    }
    if (key < n->key)
        insert(n->left, key);
    else
        insert(n->right, key);

    balance(n);
}

void erase(T* &n, int key)
{
    if (n == nil)  return ;

    if (key < n->key)
        erase(n->left, key);
    else if (key > n->key)
        erase(n->right, key);
    else {
        if (n->left == nil && n->right == nil)
            delete n, n = nil;
        else {
            (n->left->priority > n->right->priority) ? rotleft(n) : rotright(n);
            erase(n, key);
        }
    }
    if (n != nil)  getc(n);
}

int lookup(T* n, int cnt)
{
    if (cnt == n->left->cnt + 1)
        return n->key;

    if (cnt <= n->left->cnt)
        return lookup(n->left, cnt);
    else
        return lookup(n->right, cnt - (n->left->cnt + 1));
}

int main(void)
{
    FILE *fi = fopen(iname, "r"),
         *fo = fopen(oname, "w");
    int n;
    fscanf(fi, "%d\n", &n);

    init(R);
    for (int i = 1; i <= n; ++ i)
        insert(R, i);

    int ram = n, key;
    for (int k = 2, stp = 0; stp < n; ++stp, --ram) {
        k = k + (stp % ram);
        if (k > ram)
            k -= ram;
        key = lookup(R, k), fprintf(fo, "%d ", key), erase(R, key);
        if (k >= ram)
            k = 1;
    }
    fclose(fi), fclose(fo);
    return 0;
}