Advertisement
double_trouble

Untitled

Jan 30th, 2016
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.86 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <cmath>
  6. #include <string>
  7. #include <algorithm>
  8. #include <string>
  9. #include <deque>
  10. #include <iomanip>
  11. #include <cstddef>
  12.  
  13. #define F first
  14. #define S second
  15.  
  16. using namespace std;
  17.  
  18.  
  19. const long double eps = 0.000000005;
  20. const long double pi = 3.1415926535897932;
  21. const long double inf = 1e9;
  22.  
  23. struct node
  24. {
  25.     node* l;
  26.     node* r;
  27.     int v;
  28.     int p;
  29.     int w;
  30.     node()
  31.     {
  32.         l = nullptr;
  33.         r = nullptr;
  34.         v = 0;
  35.         p = rand();
  36.         w = 1;
  37.     }
  38.     node(int _v)
  39.     {
  40.         l = nullptr;
  41.         r = nullptr;
  42.         v = _v;
  43.         p = rand();
  44.         w = 1;
  45.     }
  46. };
  47.  
  48. using pnode = node*;
  49.  
  50. int weight(pnode& t)
  51. {
  52.     if (t == nullptr)
  53.         return 0;
  54.     else
  55.         return t->w;
  56. }
  57.  
  58. void upd(pnode& t)
  59. {
  60.     /*if (t == nullptr)
  61.         t->w = 0;
  62.     else*/
  63.     if (t)
  64.         t->w = weight(t->l) + weight(t->r) + 1;
  65. }
  66.  
  67. void split(pnode t, pnode& t1, pnode& t2, int k)
  68. {
  69.     if (t == nullptr)
  70.     {
  71.         t1 = nullptr;
  72.         t2 = nullptr;
  73.         return;
  74.     }
  75.  
  76.  
  77.     if (weight(t->l) >= k)
  78.     {
  79.         split(t->l, t1, t->l, k);
  80.         t2 = t;
  81.     }
  82.     else
  83.     {
  84.         split(t->r, t->r, t2, k - weight(t->l) - 1);
  85.         t1 = t;
  86.     }
  87.     upd(t);
  88. }
  89.  
  90. void merge(pnode& t, pnode l, pnode r)
  91. {
  92.     if (l == nullptr || r == nullptr)
  93.         t = l ? l : r;
  94.     else
  95.     {
  96.         if (l->p > r->p)
  97.         {
  98.  
  99.             merge(l->r, l->r, r);
  100.             t = l;
  101.         }
  102.         else
  103.         {
  104.             merge(r->l, l, r->l);
  105.             t = r;
  106.         }
  107.     }
  108.     upd(t);
  109. }
  110.  
  111.  
  112. int main()
  113. {
  114.     ios_base::sync_with_stdio(0);
  115.     //freopen("input.txt", "r", stdin);
  116.     //    freopen("output.txt", "w", stdout);
  117.  
  118.     int n, k;
  119.     cin >> n >> k;
  120.  
  121.     k--;
  122.  
  123.     pnode t = nullptr, m = nullptr, r = nullptr, l = nullptr;
  124.    
  125.     //upd(t);
  126.     for (int i = 0; i < n; i++)
  127.     {
  128.         merge(t, t, new node(i + 1));
  129.     }
  130.  
  131.  
  132.     for (int i = 0; i < n; i++)
  133.     {
  134.         split(t, l, r, k % t->w);
  135.         split(r, m, r, 1);
  136.         cout << m->v << " ";
  137.         merge(t, r, l);
  138.     }
  139.  
  140.     return 0;
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement