Cod sursa(job #3301197)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 23 iunie 2025 00:41:30
Problema Schi Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <random>
#include <cassert>

std::ifstream fin("schi.in");
std::ofstream fout("schi.out");

#define sz(x) (x == nullptr ? 0 : x->size)
#define pr(x) (x == nullptr ? -1 : x->prio)

struct Node {
    Node *l, *r;
    int32_t val, prio;
    int32_t size;

    Node(int32_t v) {
        val = v; prio = rand();
        size = 1;
        l = r = nullptr;
    }
    Node(Node* _l, int v, int p, Node *_r) {
        l = _l; r = _r;
        val = v; prio = p;
        size = sz(_l) + 1 + sz(_r);
    }
};

Node* merge(Node* l, Node *r) {
    if(l == nullptr) return r;
    if(r == nullptr) return l;

    if(pr(l) > pr(r)) return new Node(merge(l, r->l), r->val, pr(r), r->r);
    else return new Node(l->l, l->val, pr(l), merge(l->r, r));
}

std::pair<Node*, Node*> split(Node* t, int k) {
    if(t == nullptr) { assert(k == 0); return {t, t}; }

    if(k <= sz(t->l)) {
        auto s = split(t->l, k);
        return {s.first, new Node(s.second, t->val, pr(t), t->r)};
    } else {
        auto s = split(t->r, k - 1 - sz(t->l));
        return {new Node(t->l, t->val, pr(t), s.first), s.second};
    }
}

int get_kth(Node *t, int k) {
    auto s1 = split(t, k);
    auto s2 = split(s1.first, k - 1);
    // s2.second = nodul cautat
    return s2.second->val;
}

void _read(Node *t, std::vector<int>& v) {
    if(t == nullptr) return;
    _read(t->l, v); 
    v.push_back(t->val); 
    _read(t->r, v);
}

int main() {
    Node * t = nullptr;
    int n; fin >> n;
    for(int i = 1; i <= n; i++) {
        int poz; fin >> poz;
        auto [l, r] = split(t, poz - 1);
        t = merge(l, merge(new Node(i), r));
    }
    std::vector<int> v; _read(t, v);
    for(auto e : v) fout << e << '\n';
}