Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct item {
  6.     int x, y, sz;
  7.     item* l, *r;
  8.     item() {
  9.         this->l = NULL;
  10.         this->r = NULL;
  11.     }
  12.     /*
  13.     item(int x, int y) {
  14.         this->x = x;
  15.         this->y = y;
  16.         this->l = NULL;
  17.         this->r = NULL;
  18.         this->sz = 1;
  19.     }
  20.     */
  21.     item(int x, int y) : x(x), y(y), l(NULL), r(NULL), sz(1) {}
  22. };
  23.  
  24. int get_random() {
  25.     return (1ll * rand()) << 16 + rand();
  26. }
  27.  
  28. item* merge(item* a, item* b) {
  29.     if (a == NULL) {
  30.         return b;
  31.     } else if (b == NULL) {
  32.         return a;
  33.     }
  34.     if (a->y > b->y) {
  35.         a->r = merge(a->r, b);
  36.         a->sz = (a->r ? a->r->sz : 0) + (a->l ? a->l->sz : 0) + 1;
  37.         return a;
  38.     } else {
  39.         b->l = merge(a, b->l);
  40.         b->sz = (b->r ? b->r->sz : 0) + (b->l ? b->l->sz : 0) + 1;
  41.         return b;
  42.     }
  43. }
  44.  
  45. void split_by_size(item* v, item* &l, item* &r, int cnt) {
  46.     if (!v) {
  47.         l = r = NULL;
  48.         return;
  49.     }
  50.     int part = v->l ? v->l->sz : 0;
  51.     if (part + 1 <= cnt) {
  52.         split_by_size(v->r, v->r, r, cnt - part - 1);
  53.         l = v;
  54.     } else {
  55.         split_by_size(v->l, l, v->l, cnt);
  56.         r = v;
  57.     }
  58.     v->sz = (v->r ? v->r->sz : 0) + (v->l ? v->l->sz : 0) + 1;
  59. }
  60.  
  61. void split_by_key(item* v, item* &l, item* &r, int key) {
  62.     if (!v) {
  63.         l = r = NULL;
  64.         return;
  65.     }
  66.     if (v->x <= key) {
  67.         split_by_key(v->r, v->r, r, key);
  68.         l = v;
  69.     } else {
  70.         split_by_key(v->l, l, v->l, key);
  71.         r = v;
  72.     }
  73.     v->sz = (v->r ? v->r->sz : 0) + (v->l ? v->l->sz : 0) + 1;
  74. }
  75.  
  76. int main() {
  77.     srand(time(NULL));
  78.     int n, k;
  79.     cin >> n >> k;
  80.     item* root = new item(1, get_random());
  81.     for (int i = 2; i <= n; i++) {
  82.         item* new_item = new item(i, get_random());
  83.         root = merge(root, new_item);
  84.     }
  85.     int last_removed = 0;
  86.     for (int i = 1; i <= n; i++) {
  87.         item* l = NULL, *r = NULL;
  88.         int pos = k % root->sz;
  89.         if (!pos) {
  90.             pos = root->sz;
  91.         }
  92.         split_by_key(root, l, r, last_removed);
  93.         int r_sz = r ? r->sz : 0;
  94.         if (r_sz >= pos) {
  95.             item* l1 = NULL, *r1 = NULL, *l2 = NULL, *r2 = NULL;
  96.             split_by_size(r, l1, r1, pos - 1);
  97.             split_by_size(r1, l2, r2, 1);
  98.             printf("%d ", l2->x);
  99.             last_removed = l2->x;
  100.             delete l2;
  101.             root = merge(l, merge(l1, r2));
  102.         } else {
  103.             item* l1 = NULL, *r1 = NULL, *l2 = NULL, *r2 = NULL;
  104.             pos -= r_sz;
  105.             split_by_size(l, l1, r1, pos - 1);
  106.             split_by_size(r1, l2, r2, 1);
  107.             printf("%d ", l2->x);
  108.             last_removed = l2->x;
  109.             delete l2;
  110.             root = merge(merge(l1, r2), r);
  111.         }
  112.     }
  113.     cout<<endl;
  114.     //cout<<RAND_MAX<<endl;
  115.     return 0;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement