my bulky code:


#include <iostream>


class RedBlackTreeWithoutRepeatedElements {

  private:

    static const int BAD_KEY = - 1;

    static enum TypeOfRotation {LEFT, RIGHT};

    static enum NodeColor {RED, BLACK};

    struct Node {

      int key;
      Node *left, *right, *parent;
      NodeColor color;
      int total_number_of_nodes_in_subtree_with_this_node_as_root;

      Node(int m_key) : key(m_key),
                        left(NULL), right(NULL), parent(NULL),
                        color(RED),
                        total_number_of_nodes_in_subtree_with_this_node_as_root(1) {}
    };

    Node *root_, *nil_delimiter;


    void inorderedWalkWithNodeDeletion(Node *node) {
      if ( node != nil_delimiter ) {
        inorderedWalkWithNodeDeletion(node->left);
        Node *root_of_right_subtree = node->right;
        delete node;
        inorderedWalkWithNodeDeletion(root_of_right_subtree);
      }
    }


    void rotate(Node *node, TypeOfRotation type_of_rotation) {

      if ( node == nil_delimiter ) {
        return;
      }

      Node *substitutor_node = (type_of_rotation == LEFT) ? node->right : node->left;
      if ( node == nil_delimiter ) {
        return;
      }

      if ( type_of_rotation == LEFT ) {
        node->right = substitutor_node->left;
        if ( substitutor_node->left != nil_delimiter ) {
          substitutor_node->left->parent = node;
        }
        substitutor_node->left = node;
      }
      else {
        node->left = substitutor_node->right;
        if ( substitutor_node->right != nil_delimiter ) {
          substitutor_node->right->parent = node;
        }
        substitutor_node->right = node;
      }

      substitutor_node->parent = node->parent;
      if ( node != root_ ) {
        if ( node == node->parent->left ) {
          node->parent->left = substitutor_node;
        }
        else {
          node->parent->right = substitutor_node;
        }
      }
      else {
        root_ = substitutor_node;
      }
      node->parent = substitutor_node;

      substitutor_node->total_number_of_nodes_in_subtree_with_this_node_as_root =
        node->total_number_of_nodes_in_subtree_with_this_node_as_root;
      node->total_number_of_nodes_in_subtree_with_this_node_as_root =
        node->left->total_number_of_nodes_in_subtree_with_this_node_as_root +
        node->right->total_number_of_nodes_in_subtree_with_this_node_as_root + 1;
    }


    void correctPropertiesOfRedBlackTreeAfterInsertion(Node *node) {

      while ( node->parent->color == RED ) {

        Node *grandparent_node = node->parent->parent;

        Node *uncle_node = (node->parent == grandparent_node->left) ?
          grandparent_node->right : grandparent_node->left;

        if ( uncle_node->color == RED ) {
          uncle_node->color = node->parent->color = BLACK;
          grandparent_node->color = RED;
          node = grandparent_node;
        }
        else {

          if ( node->parent == grandparent_node->left ) {
            if ( node == node->parent->right ) {
              rotate(node->parent, LEFT);
              node = node->left;
            }
          }
          else {
            if ( node == node->parent->left ) {
              rotate(node->parent, RIGHT);
              node = node->right;
            }
          }

          node->parent->color = BLACK;
          grandparent_node->color = RED;
          rotate(grandparent_node, (node->parent == grandparent_node->left) ? RIGHT : LEFT );
        }
      }

      root_->color = BLACK;
    }


    void correctPropertiesOfRedBlackTreeAfterDelettion(Node *node) {

      while ( node != root_ && node->color == BLACK ) {

        if ( node == node->parent->left ) {

          Node *sibling_node = node->parent->right;

          if ( sibling_node->color == RED ) {
            sibling_node->color = BLACK;
            node->parent->color = RED;
            rotate(node->parent, LEFT);
            sibling_node = node->parent->right;
          }

          if ( sibling_node->left->color == BLACK && sibling_node->right->color == BLACK ) {
            sibling_node->color = RED;
            node = node->parent;
          }
          else {

            if ( sibling_node->right->color == BLACK ) {
              sibling_node->left->color = BLACK;
              sibling_node->color = RED;
              rotate(sibling_node, RIGHT);
              sibling_node = node->parent->right;
            }

            sibling_node->color = node->parent->color;
            node->parent->color = BLACK;
            sibling_node->right->color = BLACK;
            rotate(node->parent, LEFT);
            node = root_;
          }
        }
        else {

          Node *sibling_node = node->parent->left;

          if ( sibling_node->color == RED ) {
            sibling_node->color = BLACK;
            node->parent->color = RED;
            rotate(node->parent, RIGHT);
            sibling_node = node->parent->left;
          }

          if ( sibling_node->left->color == BLACK && sibling_node->right->color == BLACK ) {
            sibling_node->color = RED;
            node = node->parent;
          }
          else {

            if ( sibling_node->left->color == BLACK ) {
              sibling_node->right->color = BLACK;
              sibling_node->color = RED;
              rotate(sibling_node, LEFT);
              sibling_node = node->parent->left;
            }

            sibling_node->color = node->parent->color;
            node->parent->color = BLACK;
            sibling_node->left->color = BLACK;
            rotate(node->parent, RIGHT);
            node = root_;
          }
        }
      }

      node->color = BLACK;
    }


    void removeNode(Node *node) {

      Node *node_to_be_actually_deleted;

      if ( node->left == nil_delimiter || node->right == nil_delimiter ) {
        node_to_be_actually_deleted = node;
      }
      else {
        node_to_be_actually_deleted = node->right;
        while ( node_to_be_actually_deleted->left != nil_delimiter ) {
          node_to_be_actually_deleted = node_to_be_actually_deleted->left;
        }
      }

      --node_to_be_actually_deleted->total_number_of_nodes_in_subtree_with_this_node_as_root;
      Node *current_node = node_to_be_actually_deleted->parent;
      while ( current_node != nil_delimiter ) {
        --current_node->total_number_of_nodes_in_subtree_with_this_node_as_root;
        current_node = current_node->parent;
      }

      Node *only_child_of_node_to_be_actually_deleted =
        (node_to_be_actually_deleted->left != nil_delimiter) ? node_to_be_actually_deleted->left :
                                                               node_to_be_actually_deleted->right;

      only_child_of_node_to_be_actually_deleted->parent =
        node_to_be_actually_deleted->parent;

      if ( node_to_be_actually_deleted->parent != nil_delimiter ) {
        if ( node_to_be_actually_deleted == node_to_be_actually_deleted->parent->left ) {
          node_to_be_actually_deleted->parent->left = only_child_of_node_to_be_actually_deleted;
        }
        else {
          node_to_be_actually_deleted->parent->right = only_child_of_node_to_be_actually_deleted;
        }
      }
      else {
        root_ = only_child_of_node_to_be_actually_deleted;
      }

      if ( node != node_to_be_actually_deleted ) {
        node->key = node_to_be_actually_deleted->key;
      }

      if ( node_to_be_actually_deleted->color == BLACK ) {
        correctPropertiesOfRedBlackTreeAfterDelettion(only_child_of_node_to_be_actually_deleted);
      }

      delete node_to_be_actually_deleted;
    }


    Node* find_k_th_element(int k, Node *root_of_subtree) {

      int r = root_of_subtree->left->total_number_of_nodes_in_subtree_with_this_node_as_root + 1;

      if ( r == k ) {
        return root_of_subtree;
      }
      else if ( r > k ) {
        find_k_th_element(k, root_of_subtree->left);
      }
      else {
        find_k_th_element(k - r, root_of_subtree->right);
      }
    }


  public:

    RedBlackTreeWithoutRepeatedElements() {
      nil_delimiter = new Node(BAD_KEY);
        nil_delimiter->color = BLACK;
        nil_delimiter->left = nil_delimiter->right = nil_delimiter;
        nil_delimiter->total_number_of_nodes_in_subtree_with_this_node_as_root = 0;
      root_ = nil_delimiter;
    }


    void insert(int new_key) {

      if ( root_ == nil_delimiter ) {
        root_ = new Node(new_key);
          root_->color = BLACK;
          root_->left = root_->right = root_->parent = nil_delimiter;
        return;
      }

      Node *current_node = root_, *parent_node = nil_delimiter, *new_node = new Node(new_key);
        new_node->left = new_node->right = nil_delimiter;

      while ( current_node != nil_delimiter ) {
        ++current_node->total_number_of_nodes_in_subtree_with_this_node_as_root;
        parent_node = current_node;
        current_node = (current_node->key > new_key) ? current_node->left : current_node->right;
      }

      if ( parent_node->key > new_key ) {
        parent_node->left = new_node;
      }
      else {
        parent_node->right = new_node;
      }
      new_node->parent = parent_node;

      correctPropertiesOfRedBlackTreeAfterInsertion(new_node);
    }


    int getKeyOfKthElementAndRemoveIt(int k) {
      Node *k_th_element = find_k_th_element(k, root_);
      int key_of_k_th_element = k_th_element->key;
      removeNode(k_th_element);
      return key_of_k_th_element;
    }


    int getSize() const {
      return (root_ != nil_delimiter) ?
        root_->total_number_of_nodes_in_subtree_with_this_node_as_root : 0;
    }


    ~RedBlackTreeWithoutRepeatedElements() {
      inorderedWalkWithNodeDeletion(root_);
      delete nil_delimiter;
    }
};



int main() {

  int number_of_soldiers, number_of_words_in_counting_out_rhyme;

  std::cin >> number_of_soldiers >> number_of_words_in_counting_out_rhyme;

  RedBlackTreeWithoutRepeatedElements soldiers;

  for ( int soldier_id = 1; soldier_id <= number_of_soldiers; ++soldier_id ) {
    soldiers.insert(soldier_id);
  }


   int start_position_for_counting = 1, position_of_excluded_solider;

    while ( soldiers.getSize() > 1 ) {
      position_of_excluded_solider =
        start_position_for_counting + number_of_words_in_counting_out_rhyme - 1;
      if ( position_of_excluded_solider > soldiers.getSize() ) {
        position_of_excluded_solider =
          (number_of_words_in_counting_out_rhyme -
            (soldiers.getSize() - start_position_for_counting + 1)) % soldiers.getSize();
        if ( position_of_excluded_solider == 0 ) {
          position_of_excluded_solider = soldiers.getSize();
        }
      }
      std::cout << soldiers.getKeyOfKthElementAndRemoveIt(position_of_excluded_solider) << " ";
      start_position_for_counting = (position_of_excluded_solider <= soldiers.getSize()) ?
        position_of_excluded_solider : 1;
    }

    std::cout << soldiers.getKeyOfKthElementAndRemoveIt(1);

#if !defined(ONLINE_JUDGE)
  std::cin.ignore(std::cin.rdbuf()->in_avail());
  std::cin.get();
#endif

  return 0;
}


Edited by author 16.01.2012 16:24

Edited by author 16.01.2012 16:39