Pagini recente » Cod sursa (job #428615) | Cod sursa (job #182927) | Cod sursa (job #1219868) | Cod sursa (job #2600686) | Cod sursa (job #222326)
Cod sursa(job #222326)
#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;
}