Cod sursa(job #3350659)

Utilizator TraianQTraianQ TraianQ Data 11 aprilie 2026 16:43:07
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#include <stdlib.h>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
class Nod {
    public:
        int key, priority;
        int nr_nodes;
        Nod *left, *right;
        Nod(int key) {
            this->key = key;
            priority = rand();
            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;
}

void update_size(Nod *n) {
    if(n)
        n->nr_nodes = 1 + get_size(n->left) + get_size(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);
        return {s.first, n};
    }
    else {
        pt s = split(n->right, k - left_size - 1);
        n->right = s.first;
        update_size(n);
        return {n, s.second};
    }
}

Nod* merge(Nod *A, Nod *B) {
    if(A==NULL)
        return B;
    if(B==NULL)
        return A;

    if(B->priority < A->priority) {
        A->right = merge(A->right, B);
        update_size(A);
        return A;
    }
    else {
        B->left = merge(A, B->left);
        update_size(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, extra_shit = 0;
    for(int i = 1; i <= n; i++) {
        poz = (poz + i - 1) % root->nr_nodes;
        root = del(root, poz);
        fout<<eliminated->key<<" ";
        DFSfree(eliminated);
        // extra_shit = 1;
    }
    fin.close();
    fout.close();
    return 0;
}