Pagini recente » Cod sursa (job #1936160) | Cod sursa (job #969668) | Cod sursa (job #2145805) | Cod sursa (job #287751) | Cod sursa (job #3301197)
#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';
}