Pagini recente » Cod sursa (job #2982760) | Cod sursa (job #766108) | Cod sursa (job #1273280) | Cod sursa (job #2193324) | Cod sursa (job #3301081)
#include<fstream>
#include <stdlib.h>
#include <time.h>
using namespace std;
ifstream in ("schi.in");
ofstream out ("schi.out");
struct node {
int size;
int randv;
int ind;
node * left;
node * right;
node (int indx) {
this->size = 1;
this->randv = rand();
this->ind = indx;
this->left = NULL;
this->right = NULL;
}
};
node * merge (node * ltree, node * rtree) {
if (ltree== NULL) {
return rtree;
}
if (rtree == NULL) {
return ltree;
}
if (ltree == rtree) {
return ltree;
}
if (ltree->randv < rtree->randv) {
ltree->size += rtree->size;
ltree->right = merge (ltree->right, rtree);
return ltree;
}
else {
rtree->size += ltree->size;
rtree->left = merge (ltree, rtree->left);
return rtree;
}
}
pair<node*, node*> split(node * root, int x) {
if (root == NULL) {
return {NULL, NULL};
}
int l_size = root->left == NULL ? 0 : root->left->size;
if (l_size == x) {
root->size -= l_size;
node * aux = root->left;
root->left=NULL;
return {aux, root};
}
if (l_size < x) {
// go right
root->size -= root->right == NULL ? 0 : root->right->size;
pair<node*, node*> trees = split (root->right, x - (l_size+1));
root->right = NULL;
return {merge (root, trees.first), trees.second};
}
else {
// go left
root->size -= root->left == NULL? 0 :root->left->size;
pair<node*, node*> trees = split (root->left, x);
root->left = NULL;
return {trees.first, merge (trees.second, root)};
}
}
node * insert (int x, int ind, node * root) {
if (root == NULL) {
return new node(ind);
}
pair<node*, node*>trees = split (root, x-1);
return merge ( merge (trees.first, new node(ind)) , trees.second);
}
void print_order (node * root) {
if (root == NULL) {
return;
}
print_order (root->left);
out << root->ind <<"\n";
print_order (root->right);
}
int main (void) {
srand(time(NULL));
int N, X;
node * root = NULL;
in >> N;
for (int i = 1; i <= N; i ++) {
in >> X;
root = insert (X, i, root);
}
print_order (root);
return 0;
}