Cod sursa(job #222471)

Utilizator MariusMarius Stroe Marius Data 22 noiembrie 2008 17:41:40
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <cstdio>
#include <algorithm>

using namespace std;

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

#define getc(n)  ((n)->cnt = (n)->l->cnt + (n)->r->cnt + 1)

struct T {
    int key, cnt, p;
    T *l, *r;
} *R, *nil;


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

    R = nil = new T();
    nil->key = nil->cnt = nil->p = 0,
            nil->l = nil->r = NULL;
}

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

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

void balance(T* &n)
{
    if (n->l->p > n->p)
        rotleft(n);
    else if (n->r->p > n->p)
        rotright(n);
}

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

    balance(n);
}

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

    if (key < n->key)
        erase(n->l, key);
    else if (key > n->key)
        erase(n->r, key);
    else {
        if (n->cnt == 1)
            delete n, n = nil;
        else {
            (n->l->p > n->r->p) ? rotleft(n) : rotright(n);
            erase(n, key);
        }
    }
    if (n != nil)  getc(n);
}

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

    if (cnt <= n->l->cnt)
        return lookup(n->l, cnt);
    else
        return lookup(n->r, cnt - (n->l->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;
}