Advertisement
Guest User

Untitled

a guest
Dec 16th, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <memory>
  4. #include <string>
  5. #include <random>
  6.  
  7. static const size_t max_pririty = 1000000;
  8.  
  9. struct Shift {
  10. size_t left, right, move;
  11. };
  12.  
  13. std::vector<Shift> ReadInput() {
  14. size_t number;
  15. std::cin >> number;
  16. std::vector<Shift> shifts(number);
  17. for (auto &shift : shifts) {
  18. size_t left, right, move;
  19. std::cin >> left >> right >> move;
  20. --left;
  21. --right;
  22. shift = {left, right, move};
  23. }
  24. return shifts;
  25. }
  26.  
  27. class IKTreap {
  28. struct Node {
  29. Node() {}
  30. Node(char letter_, int priority_)
  31. : letter(letter_),
  32. priority(priority_),
  33. size(1),
  34. left(nullptr),
  35. right(nullptr) {}
  36. char letter;
  37. int priority;
  38. size_t size;
  39. std::shared_ptr<Node> left;
  40. std::shared_ptr<Node> right;
  41. void InOrder(std::shared_ptr<Node> node, std::string *line) {
  42. if (!node) {
  43. return;
  44. }
  45. InOrder(node->left, line);
  46. line->push_back(node->letter);
  47. InOrder(node->right, line);
  48. }
  49. std::string GetString() {
  50.  
  51. std::string line = "";
  52. InOrder(this->left, &line);
  53. line.push_back(this->letter);
  54. InOrder(this->right, &line);
  55. return line;
  56. }
  57. };
  58.  
  59. using shared_ptr = std::shared_ptr<Node>;
  60. public:
  61. explicit IKTreap(const std::string &line) {
  62. for (char letter : line) {
  63. shared_ptr node_to_add = std::make_shared<Node>(Node(letter, rand() % max_pririty));
  64. head = Merge(head, node_to_add);
  65. }
  66. }
  67. void MakeShift(Shift shift) {
  68. shared_ptr left_n_middle = nullptr;
  69. shared_ptr left = nullptr;
  70. shared_ptr right = nullptr;
  71. shared_ptr middle = nullptr;
  72. shared_ptr left_for_split = nullptr;
  73. shared_ptr right_for_split = nullptr;
  74. // std::cout << "Split: " << std::endl;
  75. // if (head) std::cout << "head: " << head->GetString() << std::endl;
  76. Split(head, shift.right + 1, &left_n_middle, &right);
  77. // if (left_n_middle) std::cout << "left_n_middle: " << left_n_middle->GetString() << std::endl;
  78. if(right) std::cout << "right: " << right->GetString() << std::endl;
  79. Split(left_n_middle, shift.left, &left, &middle);
  80. if (left) std::cout << "left: " << left->GetString() << std::endl;
  81. if (middle) std::cout << "middle: " << middle->GetString() << std::endl;
  82. Split(middle, shift.move, &left_for_split, &right_for_split);
  83. std::cout << "left_for_split: " << left_for_split->GetString() << std::endl;
  84. std::cout << "right_for_split: " << right_for_split->GetString() << std::endl;
  85. middle = Merge(right_for_split, left_for_split);
  86. std::cout << "middle: " << middle->GetString() << std::endl;
  87. left_n_middle = Merge(left, middle);
  88. std::cout << "left_n_middle: " << left_n_middle->GetString() << std::endl;
  89. head = Merge(left_n_middle, right);
  90. std::cout << "head: " << head->GetString() << std::endl;
  91. }
  92.  
  93. std::string GetString() {
  94. std::string line = "";
  95. InOrder(head, &line);
  96. return line;
  97. }
  98. private:
  99.  
  100. shared_ptr head;
  101.  
  102. void Split(shared_ptr split_node, size_t key, shared_ptr *left, shared_ptr *right) {
  103. if (!split_node) {
  104. *left = nullptr;
  105. *right = nullptr;
  106. return;
  107. }
  108. size_t left_size = Size(split_node->left);
  109. if (left_size >= key) {
  110. Split(split_node->left, key, left, right);
  111. split_node->left = *right;
  112. Update(split_node);
  113. *right = split_node;
  114. } else {
  115. Split(split_node->right, key - left_size - 1, left, right);
  116. split_node->right = *left;
  117. Update(split_node);
  118. *left = split_node;
  119. }
  120. }
  121. shared_ptr Merge(shared_ptr left, shared_ptr right) {
  122. if (!left) {
  123. return right;
  124. }
  125. if (!right) {
  126. return left;
  127. }
  128. if (left->priority > right->priority) {
  129. left->right = Merge(left->right, right);
  130. Update(left);
  131. return left;
  132. } else {
  133. right->left = Merge(left, right->left);
  134. Update(right);
  135. return right;
  136. }
  137. }
  138. void Update(shared_ptr node) {
  139. if (!node) {
  140. return;
  141. } else {
  142. node->size = 1 + Size(node->left) + Size(node->right);
  143. }
  144. }
  145. size_t Size(shared_ptr node) {
  146. if (!node) {
  147. return 0;
  148. } else {
  149. return node->size;
  150. }
  151. }
  152.  
  153. void InOrder(shared_ptr node, std::string *line) {
  154. if (!node) {
  155. return;
  156. }
  157. InOrder(node->left, line);
  158. line->push_back(node->letter);
  159. InOrder(node->right, line);
  160. }
  161. };
  162.  
  163.  
  164. std::string ProcessShifts(const std::string &line,
  165. const std::vector<Shift> & shifts) {
  166. IKTreap treap(line);
  167. std::cout << treap.GetString() << std::endl;
  168. for (size_t i = 0; i < shifts.size(); ++i) {
  169. treap.MakeShift(shifts[shifts.size() - 1 - i]);
  170. std::cout << treap.GetString() << std::endl;
  171. }
  172. return treap.GetString();
  173. }
  174.  
  175. int main() {
  176. std::string line;
  177. std::cin >> line;
  178. std::vector<Shift> shifts = ReadInput();
  179. std::string result = ProcessShifts(line, shifts);
  180. std::cout << result << std::endl;
  181. return 0;
  182. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement