Cod sursa(job #3301081)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 21 iunie 2025 14:59:05
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#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;
}