Järjestys

#include <bits/stdc++.h>

using namespace std;

struct node{
  int prior, val, size, m;
  bool c;
  node* left;
  node* right;
  node(int v){
    val = v, size = 1, c = 0, m=v;
    left=nullptr;
    right=nullptr;
    prior=rand();
  }
};

int cnt(node* t){
  if(t==nullptr) return 0;
  else return t->size;
}
int M(node* t){
  if(t==nullptr) return 0;
  else return t->m;
}
void upd(node* t){
  if(t==nullptr) return;
  t->size = cnt(t->left) + 1 + cnt(t->right);
  t->m = max(t->val, M(t->left));
  t->m = max(t->m, M(t->right));
}
void push(node* t){
  if(t==nullptr) return;
  if(t->c) {
    swap(t->left, t->right);
    if(t->left != nullptr) t->left->c = !t->left->c;
    if(t->right != nullptr) t->right->c = !t->right->c;
    t->c=0;
  }
}
void split(node* t, node*& left, node*& right, int k){
  if(t==nullptr){
    left=nullptr, right=nullptr;
    return;
  }
  push(t);
  if(cnt(t->left) >= k){
    split(t->left, left, t->left, k);
    right=t;
  }else{
    split(t->right, t->right, right, k-cnt(t->left)-1);
    left=t;
  }
  upd(left);
  upd(right);
}
void merge(node*& t, node* left, node* right){
  push(left);
  push(right);
  if(left==nullptr) t=right;
  else if(right==nullptr) t=left;
  else{
    if(left->prior > right->prior){
      merge(left->right, left->right, right);
      t=left;
    }else{
      merge(right->left, left, right->left);
      t=right;
    }
  }
  upd(t);
}
int etsi(node* t){
  push(t);
  if(t->val==t->m) return cnt(t->left)+1;
  else if(M(t->left) == t->m) return etsi(t->left);
  else return cnt(t->left) + 1 + etsi(t->right);
  upd(t);
}
vector<int> v;
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  node* tree = nullptr;
  for(int i=0; i<n; ++i){
    int a; cin >> a;
    node* t = new node(a);
    merge(tree, tree, t);
  }
  for(int i=n; i>1; --i){
    int k=etsi(tree);
    v.push_back(k);
    node* left = nullptr;
    node* right = nullptr;
    split(tree, left, right, k);
    if(left!=nullptr) left->c = !left->c;
    merge(tree, left, right);
    v.push_back(i);
    tree->c = !tree->c;
    split(tree, tree, right, i-1);
  }
  cout << v.size() << "\n";
  for(unsigned int i=0; i<v.size(); ++i) cout << v[i] << " ";
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED