Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct item {
- int x, y, sz;
- item* l, *r;
- item() {
- this->l = NULL;
- this->r = NULL;
- }
- /*
- item(int x, int y) {
- this->x = x;
- this->y = y;
- this->l = NULL;
- this->r = NULL;
- this->sz = 1;
- }
- */
- item(int x, int y) : x(x), y(y), l(NULL), r(NULL), sz(1) {}
- };
- int get_random() {
- return (1ll * rand()) << 16 + rand();
- }
- item* merge(item* a, item* b) {
- if (a == NULL) {
- return b;
- } else if (b == NULL) {
- return a;
- }
- if (a->y > b->y) {
- a->r = merge(a->r, b);
- a->sz = (a->r ? a->r->sz : 0) + (a->l ? a->l->sz : 0) + 1;
- return a;
- } else {
- b->l = merge(a, b->l);
- b->sz = (b->r ? b->r->sz : 0) + (b->l ? b->l->sz : 0) + 1;
- return b;
- }
- }
- void split_by_size(item* v, item* &l, item* &r, int cnt) {
- if (!v) {
- l = r = NULL;
- return;
- }
- int part = v->l ? v->l->sz : 0;
- if (part + 1 <= cnt) {
- split_by_size(v->r, v->r, r, cnt - part - 1);
- l = v;
- } else {
- split_by_size(v->l, l, v->l, cnt);
- r = v;
- }
- v->sz = (v->r ? v->r->sz : 0) + (v->l ? v->l->sz : 0) + 1;
- }
- void split_by_key(item* v, item* &l, item* &r, int key) {
- if (!v) {
- l = r = NULL;
- return;
- }
- if (v->x <= key) {
- split_by_key(v->r, v->r, r, key);
- l = v;
- } else {
- split_by_key(v->l, l, v->l, key);
- r = v;
- }
- v->sz = (v->r ? v->r->sz : 0) + (v->l ? v->l->sz : 0) + 1;
- }
- int main() {
- srand(time(NULL));
- int n, k;
- cin >> n >> k;
- item* root = new item(1, get_random());
- for (int i = 2; i <= n; i++) {
- item* new_item = new item(i, get_random());
- root = merge(root, new_item);
- }
- int last_removed = 0;
- for (int i = 1; i <= n; i++) {
- item* l = NULL, *r = NULL;
- int pos = k % root->sz;
- if (!pos) {
- pos = root->sz;
- }
- split_by_key(root, l, r, last_removed);
- int r_sz = r ? r->sz : 0;
- if (r_sz >= pos) {
- item* l1 = NULL, *r1 = NULL, *l2 = NULL, *r2 = NULL;
- split_by_size(r, l1, r1, pos - 1);
- split_by_size(r1, l2, r2, 1);
- printf("%d ", l2->x);
- last_removed = l2->x;
- delete l2;
- root = merge(l, merge(l1, r2));
- } else {
- item* l1 = NULL, *r1 = NULL, *l2 = NULL, *r2 = NULL;
- pos -= r_sz;
- split_by_size(l, l1, r1, pos - 1);
- split_by_size(r1, l2, r2, 1);
- printf("%d ", l2->x);
- last_removed = l2->x;
- delete l2;
- root = merge(merge(l1, r2), r);
- }
- }
- cout<<endl;
- //cout<<RAND_MAX<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement