Pagini recente » Cod sursa (job #3347376) | Cod sursa (job #3334033) | Cod sursa (job #3347853) | Cod sursa (job #3347071) | Cod sursa (job #3350683)
#include <fstream>
#include <stdlib.h>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
class Nod {
public:
int key, height;
int nr_nodes;
Nod *left, *right;
Nod(int key) {
this->key = key;
height = 1;
nr_nodes = 1;
this->left = this->right = NULL;
}
};
using pt = pair<Nod*, Nod*>;
Nod* root = NULL;
int get_size(Nod *n) {
return n ? n->nr_nodes : 0;
}
int get_height(Nod *n) {
return n ? n->height : 0;
}
void update_size(Nod *n) {
if(n)
n->nr_nodes = 1 + get_size(n->left) + get_size(n->right);
}
void update_height(Nod *n) {
if(n)
n->height = 1 + get_height(n->left) + get_height(n->right);
}
pt split(Nod *n, int k) {
if(n==NULL)
return {NULL, NULL};
int left_size = get_size(n->left);
if(k <= left_size) {
pt s = split(n->left, k);
n->left = s.second;
update_size(n);
update_height(n);
return {s.first, n};
}
else {
pt s = split(n->right, k - left_size - 1);
n->right = s.first;
update_size(n);
update_height(n);
return {n, s.second};
}
}
Nod* merge(Nod *A, Nod *B) {
if(A==NULL)
return B;
if(B==NULL)
return A;
if(B->height < A->height) {
A->right = merge(A->right, B);
update_size(A);
update_height(A);
return A;
}
else {
B->left = merge(A, B->left);
update_size(B);
update_height(B);
return B;
}
}
Nod *insert(Nod *a, int key, int k) {
Nod *new_nod = new Nod(key);
pt res = split(a, k);
return merge(merge(res.first, new_nod), res.second);
}
Nod* eliminated;
void DFSfree(Nod *a) {
if(a) {
DFSfree(a->left);
DFSfree(a->right);
free(a);
}
}
Nod *del(Nod *a, int st, int dr) {
pt p1 = split(a, st);
pt p2 = split(p1.second, dr - st + 1);
eliminated = p2.first;
return merge(p1.first, p2.second);
}
Nod *del(Nod *a, int k) {
return del(a, k, k);
}
void InOrder(Nod *a) {
if(a==NULL)
return;
InOrder(a->left);
fout<<a->key<<" ";
InOrder(a->right);
}
int main() {
srand(time(NULL));
int n;
fin>>n;
for(int i = 0; i < n; i++) {
root = insert(root, i + 1, i);
}
// InOrder(root);
int poz = 1;
for(int i = 1; i <= n; i++) {
poz = (poz + i - 1) % root->nr_nodes;
root = del(root, poz);
fout<<eliminated->key<<" ";
DFSfree(eliminated);
}
fin.close();
fout.close();
return 0;
}