Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <memory>
- #include <string>
- #include <random>
- static const size_t max_pririty = 1000000;
- struct Shift {
- size_t left, right, move;
- };
- std::vector<Shift> ReadInput() {
- size_t number;
- std::cin >> number;
- std::vector<Shift> shifts(number);
- for (auto &shift : shifts) {
- size_t left, right, move;
- std::cin >> left >> right >> move;
- --left;
- --right;
- shift = {left, right, move};
- }
- return shifts;
- }
- class IKTreap {
- struct Node {
- Node() {}
- Node(char letter_, int priority_)
- : letter(letter_),
- priority(priority_),
- size(1),
- left(nullptr),
- right(nullptr) {}
- char letter;
- int priority;
- size_t size;
- std::shared_ptr<Node> left;
- std::shared_ptr<Node> right;
- void InOrder(std::shared_ptr<Node> node, std::string *line) {
- if (!node) {
- return;
- }
- InOrder(node->left, line);
- line->push_back(node->letter);
- InOrder(node->right, line);
- }
- std::string GetString() {
- std::string line = "";
- InOrder(this->left, &line);
- line.push_back(this->letter);
- InOrder(this->right, &line);
- return line;
- }
- };
- using shared_ptr = std::shared_ptr<Node>;
- public:
- explicit IKTreap(const std::string &line) {
- for (char letter : line) {
- shared_ptr node_to_add = std::make_shared<Node>(Node(letter, rand() % max_pririty));
- head = Merge(head, node_to_add);
- }
- }
- void MakeShift(Shift shift) {
- shared_ptr left_n_middle = nullptr;
- shared_ptr left = nullptr;
- shared_ptr right = nullptr;
- shared_ptr middle = nullptr;
- shared_ptr left_for_split = nullptr;
- shared_ptr right_for_split = nullptr;
- // std::cout << "Split: " << std::endl;
- // if (head) std::cout << "head: " << head->GetString() << std::endl;
- Split(head, shift.right + 1, &left_n_middle, &right);
- // if (left_n_middle) std::cout << "left_n_middle: " << left_n_middle->GetString() << std::endl;
- if(right) std::cout << "right: " << right->GetString() << std::endl;
- Split(left_n_middle, shift.left, &left, &middle);
- if (left) std::cout << "left: " << left->GetString() << std::endl;
- if (middle) std::cout << "middle: " << middle->GetString() << std::endl;
- Split(middle, shift.move, &left_for_split, &right_for_split);
- std::cout << "left_for_split: " << left_for_split->GetString() << std::endl;
- std::cout << "right_for_split: " << right_for_split->GetString() << std::endl;
- middle = Merge(right_for_split, left_for_split);
- std::cout << "middle: " << middle->GetString() << std::endl;
- left_n_middle = Merge(left, middle);
- std::cout << "left_n_middle: " << left_n_middle->GetString() << std::endl;
- head = Merge(left_n_middle, right);
- std::cout << "head: " << head->GetString() << std::endl;
- }
- std::string GetString() {
- std::string line = "";
- InOrder(head, &line);
- return line;
- }
- private:
- shared_ptr head;
- void Split(shared_ptr split_node, size_t key, shared_ptr *left, shared_ptr *right) {
- if (!split_node) {
- *left = nullptr;
- *right = nullptr;
- return;
- }
- size_t left_size = Size(split_node->left);
- if (left_size >= key) {
- Split(split_node->left, key, left, right);
- split_node->left = *right;
- Update(split_node);
- *right = split_node;
- } else {
- Split(split_node->right, key - left_size - 1, left, right);
- split_node->right = *left;
- Update(split_node);
- *left = split_node;
- }
- }
- shared_ptr Merge(shared_ptr left, shared_ptr right) {
- if (!left) {
- return right;
- }
- if (!right) {
- return left;
- }
- if (left->priority > right->priority) {
- left->right = Merge(left->right, right);
- Update(left);
- return left;
- } else {
- right->left = Merge(left, right->left);
- Update(right);
- return right;
- }
- }
- void Update(shared_ptr node) {
- if (!node) {
- return;
- } else {
- node->size = 1 + Size(node->left) + Size(node->right);
- }
- }
- size_t Size(shared_ptr node) {
- if (!node) {
- return 0;
- } else {
- return node->size;
- }
- }
- void InOrder(shared_ptr node, std::string *line) {
- if (!node) {
- return;
- }
- InOrder(node->left, line);
- line->push_back(node->letter);
- InOrder(node->right, line);
- }
- };
- std::string ProcessShifts(const std::string &line,
- const std::vector<Shift> & shifts) {
- IKTreap treap(line);
- std::cout << treap.GetString() << std::endl;
- for (size_t i = 0; i < shifts.size(); ++i) {
- treap.MakeShift(shifts[shifts.size() - 1 - i]);
- std::cout << treap.GetString() << std::endl;
- }
- return treap.GetString();
- }
- int main() {
- std::string line;
- std::cin >> line;
- std::vector<Shift> shifts = ReadInput();
- std::string result = ProcessShifts(line, shifts);
- std::cout << result << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement