ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1521. War Games 2

Please answer what test#1 looks like. My program crashes while test#1, but all right when i run it on my computer
Posted by lenny 16 Jan 2012 16:18


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