Advertisement
FHVirus

Untitled

Oct 28th, 2020
257
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 225;
  5.  
  6. /* Start Treap*/
  7. int val[N], l[N], r[N], sz[N], cnt = 1;
  8. unsigned pri[N];
  9. inline unsigned ran(){
  10.     static unsigned x = 131;
  11.     return ++(x *= 0xdefaced);
  12. }
  13. inline int newNode(int v){
  14.     val[cnt] = v;
  15.     l[cnt] = r[cnt] = 0;
  16.     sz[cnt] = 1;
  17.     pri[cnt] = ran();
  18.     return cnt++;
  19. }
  20. inline int Sz(int x){
  21.     return x ? sz[x] : 0;
  22. }
  23. void szsplit(int o, int &a, int &b, int k){
  24.     if(!o){
  25.         a = b = 0;
  26.         return;
  27.     }
  28.     if(Sz(l[o]) + 1 <= k){
  29.         a = o;
  30.         szsplit(r[o], r[a], b, k - Sz(l[o]) - 1);
  31.     } else {
  32.         b = o;
  33.         szsplit(l[o], a, l[b], k);
  34.     }
  35. }
  36. int merge(int a, int b){
  37.     if(!a or !b) return a ? a : b;
  38.     if(pri[a] < pri[b]){
  39.         r[a] = merge(r[a], b);
  40.         return a;
  41.     }
  42.     l[b] = merge(a, l[b]);
  43.     return b;
  44. }
  45.  
  46. // void dfs(int u){
  47. //  if(l[u])dfs(l[u]);
  48. //  cout << val[u] << '\n';
  49. //  if(r[u])dfs(r[u]);
  50. // }
  51. inline void take(int &root, int p){
  52.     int a, b, c, eek;
  53.     szsplit(root, eek, c, p + 1);
  54.     szsplit(eek, a, b, p);
  55.     cout << val[b] << ' ';
  56.     root = merge(a, c);
  57. }
  58.  
  59. /* End Treap */
  60.  
  61. int n, nxt[N];
  62.  
  63. int main(){
  64.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  65.     while(cin >> n){
  66.         for(int i = 0; i < n; ++i)
  67.             cin >> nxt[i];
  68.         cnt = 1;
  69.         int root = 0;
  70.         for(int i = 1; i <= n; ++i)
  71.             root = merge(root, newNode(i));
  72.         // dfs(root);
  73.  
  74.         int p = 0, sum = n;
  75.         for(int i = 0; i < n; ++i){
  76.             p = (p + nxt[i] - 1) % sum;
  77.             take(root, p);
  78.             --sum;
  79.         }
  80.         cout << '\n';
  81.     }
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement