Järjestys

#include <iostream>
#include <vector>
#include <algorithm>

// Augmented binary tree for better average case time complexity.
// Hopefully no inputs are inoptimal. I really don't want to make
// this a red-black tree.
struct Node {
  int value;
  int lc;
  int rc;
  Node* left;
  Node* right;

  Node(int v) {
    value = v;
    lc = 0;
    rc = 0;
    left = 0;
    right = 0;
  }
};

struct BinaryTree {
  Node* root;

  BinaryTree() {
    root = 0;
  }

  void insert(int i) {
    Node* node = new Node(i);
    if (root == 0) {
      root = node;
      return;
    }
    Node* n = root;
    while(true) {
      if (n->value < i) {
        ++n->rc;
        if (n->right == 0) {
          n->right = node;
          break;
        } else {
          n = n->right;
        }
      } else if (n->value >= i) {
        ++n->lc;
        if (n->left == 0) {
          n->left = node;
          break;
        } else {
          n = n->left;
        }
      }
    }
  }

  int indexOf(int i) {
    if (root == 0) {
      return 0;
    }
    Node* n = root;
    int index = 0;
    while(true) {
      if (i == n->value) {
        return index;
      }
      if (i < n->value) {
        n = n->left;
      } else if (i > n->value) {
        index += n->lc + 1;
        n = n->right;
      }
    }
  }
};

int main() {
  int l;
  std::cin >> l;
  int* c = new int[l];
  for (int i = 0; i < l; ++i) {
    int n;
    std::cin >> n;
    c[i] = n;
  }
  /*
  Insertion sort-ish
  0: (a-b)-(c-d)-e-f || Step 1: swap elements before new one's spot
  1: (b-a)-(c-d)-e-f || Step 2: swap elements before new one
  2: (d-c)-(a-b)-e-f || Step 3: swap elements before new one, and new one
  3: e-(b-a)-(c-d)-f || Step 4: Swap elements before new one's spot and the spot
  4: (a-b)-e-(c-d)-f || DONE!
  However, finding the position we need to insert e to is an o(n) operation.
  So I'll use this augmented binary tree to find the new one's position.
  */
  // Actually you can't swap the first 0 elements :(. I'm removing 1's too since it doesn't cost any extra.
  std::vector<int> swaps;
  BinaryTree tree;
  for (int d = 0; d < l; ++d) {
    tree.insert(c[d]);
    int spot = tree.indexOf(c[d]);
    if (spot > 1) {
      if (swaps.size() != 0 && swaps[swaps.size() - 1] == spot) {
        swaps.pop_back();
      } else {
        swaps.push_back(spot);
      }
    }
    if (d > 1) {
      if (swaps.size() != 0 && swaps[swaps.size() - 1] == d) {
        swaps.pop_back();
      } else {
        swaps.push_back(d);
      }
    }
    if (d > 0) {
      if (swaps.size() != 0 && swaps[swaps.size() - 1] == d+1) {
        swaps.pop_back();
      } else {
        swaps.push_back(d+1);
      }
    }
    if (spot > 0) {
      if (swaps.size() != 0 && swaps[swaps.size() - 1] == spot+1) {
        swaps.pop_back();
      } else {
        swaps.push_back(spot+1);
      }
    }
  }
  std::cout << swaps.size() << "\n";
  for (int i = 0; i < (int)swaps.size(); ++i) {
    std::cout << swaps[i] << " ";
  }
  std::cout << "\n";
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED