Pagini recente » Cod sursa (job #2563451) | Cod sursa (job #10395) | Cod sursa (job #2347259) | Cod sursa (job #1385389) | Cod sursa (job #1266006)
#include <cstdio>
#include <iostream>
#include <vector>
struct Interval {
int left, right;
Interval(int left, int right): left(left), right(right) {}
bool contains(int value)
{
return left <= value and value < right;
}
bool has_children()
{
return left+1<right;
}
Interval leftHalf()
{
return Interval(left, (left+right)>>1);
}
Interval rightHalf()
{
return Interval((left+right)>>1, right);
}
bool contains(Interval interval)
{
return this->left <= interval.left and interval.right <= this->right;
}
int size()
{
return right - left;
}
};
struct Nod
{
int value;
Interval interval;
Nod *left, *right;
Nod(Interval interval, int value):
value(value),
interval(interval),
left(NULL),
right(NULL){}
} *root;
Nod* build_tree(Interval interval)
{
Nod *ret = new Nod(interval, interval.size());
if(interval.has_children()) {
ret->left = build_tree(interval.leftHalf());
ret->right = build_tree(interval.rightHalf());
}
return ret;
}
void remove(Nod* node, int which)
{
node->value--;
if(node->interval.has_children())
{
if(node->interval.leftHalf().contains(which))
{
remove(node->left, which);
}
else
{
remove(node->right, which);
}
}
}
int kth_element(Nod* node, int kth)
{
if(!(node->interval.has_children())) {
return node->interval.left;
}
if(node->left->value >= kth) {
return kth_element(node->left, kth);
}
return kth_element(node->right, kth - node->left->value);
}
int main ()
{
FILE *fin = fopen("order.in", "r");
FILE *fout = fopen("order.out", "w");
int n;
fscanf(fin, "%d", &n);
root = build_tree(Interval(1,n+1));
int pos=1; // pozitia in elementele existente
for(int k=1; k<n; k++)
{
pos = (pos+k-1) % (n-k+1) + 1; // salt in elementele care exista
int element = kth_element(root, pos);
fprintf(fout,"%d ", element);
remove(root, element);
pos = ( pos -1 -1 + n-k) % (n-k) +1;
}
fprintf(fout,"%d",kth_element(root,1));
return 0;
}