Pagini recente » Cod sursa (job #368317) | Cod sursa (job #103541) | Cod sursa (job #1497430) | Cod sursa (job #62829) | Cod sursa (job #225331)
Cod sursa(job #225331)
#include <fstream>
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
class Treap {
private:
struct Node {
short int value, count;
int probability;
Node *left, *right;
Node(int _value) {
value = _value;
count = 1;
probability = rand() % 1000000007;
left = right = NULL;
}
};
Node *root;
int repair_count(Node *p) {
return 1 + (p->left != NULL ? p->left->count : 0) + (p->right != NULL ? p->right->count : 0);
}
void rotleft(Node *&);
void rotright(Node *&);
void insert(Node*&, Node*&);
void remove(Node*&, int);
int find(Node*, int);
public:
Treap(): root(NULL) {
srand(time(0));
}
void insert(int value) {
Node *p = new Node(value);
insert(root, p);
}
void remove(int value) {
remove(root, value);
}
int find(int pos) {
return find(root, pos);
}
};
void Treap::rotleft(Node *&root) {
Node *p = root->right;
root->right = p->left;
p->left = root;
root->count = repair_count(root);
p->count = repair_count(p);
root = p;
}
void Treap::rotright(Node *&root) {
Node *p = root->left;
root->left = p->right;
p->right = root;
root->count = repair_count(root);
p->count = repair_count(p);
root = p;
}
void Treap::insert(Node *&root, Node *&p) {
if(root == NULL) {
root = p;
return;
}
if(p->value < root->value) {
if(root->left == NULL)
root->left = p;
else
insert(root->left, p);
root->count = repair_count(root);
if(root->probability < root->left->probability)
rotright(root);
}
else {
if(root->right == NULL)
root->right = p;
else
insert(root->right, p);
root->count = repair_count(root);
if(root->probability < root->right->probability)
rotleft(root);
}
}
void Treap::remove(Node *&root, int value) {
if(root == NULL)
return;
if(value < root->value) {
remove(root->left, value);
root->count = repair_count(root);
return;
}
if(value > root->value) {
remove(root->right, value);
root->count = repair_count(root);
return;
}
if(!root->left && !root->right) {
root = NULL;
return;
}
if(!root->left || (root->right && root->right->probability > root->left->probability)) {
rotleft(root);
remove(root->left, value);
root->count = repair_count(root);
return;
}
if(!root->right || (root->left && root->left->probability > root->right->probability)) {
rotright(root);
remove(root->right, value);
root->count = repair_count(root);
return;
}
}
int Treap::find(Node *root, int pos) {
int cnt = root->left == NULL ? 0 : root->left->count;
if(pos <= cnt)
return find(root->left, pos);
if(pos == cnt + 1)
return root->value;
return find(root->right, pos - cnt - 1);
}
int main() {
int N;
in >> N;
Treap T;
for(int i = 1; i <= N; ++i)
T.insert(i);
for(int step = 1, pos = 1, value; step <= N; ++step) {
pos = (pos + step - 1) % (N - step + 1) + 1;
out << (value = T.find(pos)) << " ";
T.remove(value);
--pos;
if(!pos)
pos = (N - step + 1) - 1;
}
return 0;
}