Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- const int N = 1e5 + 225;
- /* Start Treap*/
- int val[N], l[N], r[N], sz[N], cnt = 1;
- unsigned pri[N];
- inline unsigned ran(){
- static unsigned x = 131;
- return ++(x *= 0xdefaced);
- }
- inline int newNode(int v){
- val[cnt] = v;
- l[cnt] = r[cnt] = 0;
- sz[cnt] = 1;
- pri[cnt] = ran();
- return cnt++;
- }
- inline int Sz(int x){
- return x ? sz[x] : 0;
- }
- void szsplit(int o, int &a, int &b, int k){
- if(!o){
- a = b = 0;
- return;
- }
- if(Sz(l[o]) + 1 <= k){
- a = o;
- szsplit(r[o], r[a], b, k - Sz(l[o]) - 1);
- } else {
- b = o;
- szsplit(l[o], a, l[b], k);
- }
- }
- int merge(int a, int b){
- if(!a or !b) return a ? a : b;
- if(pri[a] < pri[b]){
- r[a] = merge(r[a], b);
- return a;
- }
- l[b] = merge(a, l[b]);
- return b;
- }
- // void dfs(int u){
- // if(l[u])dfs(l[u]);
- // cout << val[u] << '\n';
- // if(r[u])dfs(r[u]);
- // }
- inline void take(int &root, int p){
- int a, b, c, eek;
- szsplit(root, eek, c, p + 1);
- szsplit(eek, a, b, p);
- cout << val[b] << ' ';
- root = merge(a, c);
- }
- /* End Treap */
- int n, nxt[N];
- int main(){
- ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- while(cin >> n){
- for(int i = 0; i < n; ++i)
- cin >> nxt[i];
- cnt = 1;
- int root = 0;
- for(int i = 1; i <= n; ++i)
- root = merge(root, newNode(i));
- // dfs(root);
- int p = 0, sum = n;
- for(int i = 0; i < n; ++i){
- p = (p + nxt[i] - 1) % sum;
- take(root, p);
- --sum;
- }
- cout << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement