Pagini recente » Cod sursa (job #126585) | Cod sursa (job #1529064) | Cod sursa (job #2883791) | Cod sursa (job #2809940) | Cod sursa (job #222471)
Cod sursa(job #222471)
#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;
}