API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 10th, 2020
191
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 19.81 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. template<class T1, class T2>
  4. struct CasePointer {
  5.   uintptr_t value = reinterpret_cast<uintptr_t>((T1*) nullptr);
  6.   T1* operator()() const {
  7.     return reinterpret_cast<T1*>(value);
  8.   }
  9.   T1& operator*() const {
  10.     return *operator()();
  11.   }
  12.   T1* operator->() const {
  13.     return operator()();
  14.   }
  15.   bool isOther() const {
  16.     return (value & 1) != 0;
  17.   }
  18.   T2* other() {
  19.     return reinterpret_cast<T2*>(value & ~uintptr_t(1));
  20.   }
  21.   const T2* other() const {
  22.     return reinterpret_cast<const T2*>(value & ~uintptr_t(1));
  23.   }
  24.   void operator=(T1* other) {
  25.     value = reinterpret_cast<uintptr_t>(other);
  26.   }
  27.   void operator=(T2* other) {
  28.     value = reinterpret_cast<uintptr_t>(other) + 1;
  29.   }
  30.  
  31.   bool operator==(const CasePointer& other) const {
  32.     return value == other.value;
  33.   }
  34.  
  35.   bool operator!=(const CasePointer& other) const {
  36.     return value != other.value;
  37.   }
  38. };
  39.  
  40. template<class T>
  41. class TreapList {
  42.   struct Node {
  43.     T value;
  44.     uint32_t weight;
  45.     uint32_t size = 1;
  46.     CasePointer<Node, TreapList> parent;
  47.     Node* left = nullptr;
  48.     Node* right = nullptr;
  49.     Node(const T& value, uint32_t weight)
  50.         : value(value), weight(weight) {
  51.     }
  52.     Node(T&& value, uint32_t weight)
  53.         : value(std::move(value)), weight(weight) {
  54.     }
  55.     bool hasParent() const {
  56.       return !parent.isOther();
  57.     }
  58.   };
  59.   template<bool isConst = false>
  60.   struct IterImpl {
  61.     friend class IterImpl;
  62.     friend class TreapList;
  63.    private:
  64.     CasePointer<Node, TreapList> pos;
  65.  
  66.    public:
  67.     IterImpl() {
  68.     }
  69.  
  70.     IterImpl(Node* node) {
  71.       pos = node;
  72.     }
  73.     IterImpl(TreapList* rootObject) {
  74.       pos = rootObject;
  75.     }
  76.     IterImpl(TreapList* rootObject, uint32_t index) {
  77.       pos = rootObject->root;
  78.       if (pos->left != nullptr) {
  79.         *this += int32_t(index - pos->left->size);
  80.       } else {
  81.         *this += int32_t(index);
  82.       }
  83.     }
  84.     template<bool isOtherConst>
  85.     bool operator==(const IterImpl<isOtherConst>& other) const {
  86.       return pos == other.pos;
  87.     }
  88.     template<bool isOtherConst>
  89.     bool operator!=(const IterImpl<isOtherConst>& other) const {
  90.       return pos != other.pos;
  91.     }
  92.     template<bool isOtherConst, class = std::enable_if_t<isConst || !isOtherConst>>
  93.     void operator=(const IterImpl<isOtherConst>& other) {
  94.       pos = other.pos;
  95.     }
  96.     std::conditional_t<isConst, const T&, T&> operator*() const {
  97.       return pos->value;
  98.     }
  99.     std::conditional_t<isConst, const T*, T*> operator->() const {
  100.       return &pos->value;
  101.     }
  102.     IterImpl& operator++() {
  103.       if (pos.isOther()) {
  104.         // Undefined Behaviour
  105.         return *this;
  106.       }
  107.       if (pos->right != nullptr) {
  108.         pos = getFirstVertex(pos->right);
  109.         return *this;
  110.       }
  111.       while (true) {
  112.         if (!pos->hasParent()) {
  113.           pos = pos->parent.other();
  114.           return *this;
  115.         }
  116.         Node* parent = pos->parent();
  117.         if (parent->left == pos()) {
  118.           pos = parent;
  119.           return *this;
  120.         }
  121.         pos = parent;
  122.       }
  123.     }
  124.  
  125.     IterImpl& operator--() {
  126.       if (pos.isOther()) {
  127.         pos = getLastVertex(pos.other()->root);
  128.         return *this;
  129.       }
  130.       if (pos->left != nullptr) {
  131.         pos = getLastVertex(pos->left);
  132.         return *this;
  133.       }
  134.       while (true) {
  135.         if (!pos->hasParent()) {
  136.           // Undefined behaviour.
  137.           return *this;
  138.         }
  139.         Node* parent = pos->parent();
  140.         if (parent->right == pos()) {
  141.           pos = parent;
  142.           return *this;
  143.         }
  144.         pos = parent;
  145.       }
  146.     }
  147.  
  148.     uint32_t index() const {
  149.       if (pos.isOther()) {
  150.         Node* root = pos.other()->root;
  151.         if (root == nullptr) {
  152.           return 0;
  153.         }
  154.         return root->size;
  155.       }
  156.       Node* node = pos();
  157.       uint32_t result = node->left ? node->left->size : 0;
  158.       while (node->hasParent()) {
  159.         Node* parent = node->parent();
  160.         if (parent->left != nullptr) {
  161.           result += parent->left->size;
  162.         }
  163.         node = parent;
  164.       }
  165.       return result;
  166.     }
  167.  
  168.     IterImpl& operator+=(int32_t value) {
  169.       if (pos.isOther()) {
  170.         if (value >= 0) {
  171.           return *this;
  172.         }
  173.         pos = pos.other()->root;
  174.         value++;
  175.         if (pos->right != nullptr) {
  176.           value += pos->right->size;
  177.         }
  178.       }
  179.       while (value != 0) {
  180.         if (pos->left != nullptr && value < 0) {
  181.           pos = pos->left;
  182.           value++;
  183.           if (pos->right != nullptr) {
  184.             value += pos->right->size;
  185.           }
  186.           continue;
  187.         }
  188.         if (pos->right != nullptr && value > 0) {
  189.           pos = pos->right;
  190.           value--;
  191.           if (pos->left != nullptr) {
  192.             value -= pos->left->size;
  193.           }
  194.           continue;
  195.         }
  196.         if (!pos->hasParent()) {
  197.           pos = pos->parent.other();
  198.           return *this;
  199.         }
  200.         if (value > 0) {
  201.           bool good = false;
  202.           while (pos->hasParent()) {
  203.             Node* parent = pos->parent();
  204.             if (parent->left == pos()) {
  205.               value--;
  206.               pos = parent;
  207.               good = true;
  208.               break;
  209.             }
  210.             pos = parent;
  211.           }
  212.           if (!good) {
  213.             pos = pos->parent.other();
  214.             return *this;
  215.           }
  216.         } else {
  217.           bool good = false;
  218.           while (pos->hasParent()) {
  219.             Node* parent = pos->parent();
  220.             if (parent->right == pos()) {
  221.               value++;
  222.               pos = parent;
  223.               good = true;
  224.               break;
  225.             }
  226.             pos = parent;
  227.           }
  228.           if (!good) {
  229.             pos = pos->parent.other();
  230.             return *this;
  231.           }
  232.         }
  233.       }
  234.       return *this;
  235.     }
  236.  
  237.     IterImpl& operator-=(int32_t value) {
  238.       return *this += -value;
  239.     }
  240.  
  241.     IterImpl operator+(int32_t value) {
  242.       IterImpl result(*this);
  243.       result += value;
  244.       return result;
  245.     }
  246.  
  247.     IterImpl operator-(int32_t value) {
  248.       IterImpl result(*this);
  249.       result -= value;
  250.       return result;
  251.     }
  252.   };
  253.  
  254.   Node* root = nullptr;
  255.   std::ranlux48 rnd;
  256.  
  257.   static Node* getFirstVertex(Node* current) {
  258.     if (current == nullptr) {
  259.       return nullptr;
  260.     }
  261.     while (current->left != nullptr) current = current->left;
  262.     return current;
  263.   }
  264.  
  265.   static Node* getLastVertex(Node* current) {
  266.     if (current == nullptr) {
  267.       return nullptr;
  268.     }
  269.     while (current->right != nullptr) current = current->right;
  270.     return current;
  271.   }
  272.  
  273.   static uint64_t rnd64() {
  274.     uint32_t res1, res2;
  275. #ifdef __MINGW32__
  276.     asm volatile("rdrand %0" :"=a"(res1) ::"cc");
  277.     asm volatile("rdrand %0" :"=a"(res2) ::"cc");
  278. #else
  279.     {
  280.       std::random_device device;
  281.       res1 = device();
  282.       res2 = device();
  283.     }
  284. #endif
  285.     return (uint64_t(res1) << 32) + res2;
  286.   }
  287.  
  288.   Node* createNode(const T& value) {
  289.     return new Node(value, uint32_t(rnd()));
  290.   }
  291.  
  292.   Node* createNode(T&& value) {
  293.     return new Node(std::move(value), uint32_t(rnd()));
  294.   }
  295.  
  296.   void freeNodes(Node* node) {
  297.     if (node->left != nullptr) {
  298.       freeNodes(node->left);
  299.     }
  300.     if (node->right != nullptr) {
  301.       freeNodes(node->right);
  302.     }
  303.     delete node;
  304.   }
  305.  
  306.   void push_back_node(Node* node) {
  307.     if (root == nullptr) {
  308.       root = node;
  309.       root->parent = this;
  310.       node->size = 1;
  311.       return;
  312.     }
  313.     if (node->weight > root->weight) {
  314.       node->left = root;
  315.       root->parent = node;
  316.       node->parent = this;
  317.       node->size = root->size + 1;
  318.       root = node;
  319.       return;
  320.     }
  321.     Node* cur = root;
  322.     while (cur->right != nullptr) {
  323.       cur->size++;
  324.       Node* right = cur->right;
  325.       if (node->weight > right->weight) {
  326.         cur->right = node;
  327.         node->parent = cur;
  328.         node->left = right;
  329.         node->size = right->size + 1;
  330.         right->parent = node;
  331.         return;
  332.       }
  333.       cur = cur->right;
  334.     }
  335.     cur->right = node;
  336.     cur->size++;
  337.     node->parent = cur;
  338.     node->size = 1;
  339.   }
  340.  
  341.   void push_front_node(Node* node) {
  342.     if (root == nullptr) {
  343.       root = node;
  344.       root->parent = this;
  345.       node->size = 1;
  346.       return;
  347.     }
  348.     if (node->weight > root->weight) {
  349.       node->right = root;
  350.       root->parent = node;
  351.       node->parent = this;
  352.       node->size = root->size + 1;
  353.       root = node;
  354.       return;
  355.     }
  356.     Node* cur = root;
  357.     while (cur->left != nullptr) {
  358.       cur->size++;
  359.       Node* left = cur->left;
  360.       if (node->weight > left->weight) {
  361.         cur->left = node;
  362.         node->parent = cur;
  363.         node->right = left;
  364.         node->size = left->size + 1;
  365.         left->parent = node;
  366.         return;
  367.       }
  368.       cur = cur->left;
  369.     }
  370.     cur->left = node;
  371.     cur->size++;
  372.     node->parent = cur;
  373.     node->size = 1;
  374.   }
  375.  
  376.   void moveParent(Node* from, Node* to) {
  377.     to->parent = from->parent;
  378.     if (to->parent.isOther()) {
  379.       root = to;
  380.       return;
  381.     }
  382.     if (from->parent->right == from) {
  383.       from->parent->right = to;
  384.     } else {
  385.       from->parent->left = to;
  386.     }
  387.   }
  388.  
  389.   void balanceDown(Node* node) {
  390.     // node->right must be nullptr
  391.     // node->parent is normal
  392.     while (node->left != nullptr && node->left->weight > node->weight) {
  393.       Node* parent = node->parent();
  394.       Node* left = node->left;
  395.       node->left = left->right;
  396.       left->size = node->size;
  397.       node->size = 1;
  398.       if (node->left != nullptr) {
  399.         node->size += node->left->size;
  400.       }
  401.       if (node->left != nullptr) {
  402.         node->left->parent = node;
  403.       }
  404.       left->right = node;
  405.       moveParent(node, left);
  406.       node->parent = left;
  407.     }
  408.   }
  409.  
  410.   void rotateLeft(Node* parent) {
  411.     Node* node = parent->right;
  412.     parent->right = node->left;
  413.     node->size = parent->size;
  414.     parent->size = 1;
  415.     if (parent->right != nullptr) {
  416.       parent->right->parent = parent;
  417.       parent->size += parent->right->size;
  418.     }
  419.     if (parent->left != nullptr) {
  420.       parent->size += parent->left->size;
  421.     }
  422.     moveParent(parent, node);
  423.     parent->parent = node;
  424.     node->left = parent;
  425.   }
  426.  
  427.   void rotateRight(Node* parent) {
  428.     Node* node = parent->left;
  429.     parent->left = node->right;
  430.     node->size = parent->size;
  431.     parent->size = 1;
  432.     if (parent->left != nullptr) {
  433.       parent->left->parent = parent;
  434.       parent->size += parent->left->size;
  435.     }
  436.     if (parent->right != nullptr) {
  437.       parent->size += parent->right->size;
  438.     }
  439.     moveParent(parent, node);
  440.     parent->parent = node;
  441.     node->right = parent;
  442.   }
  443.  
  444.   void balanceUp(Node* node) {
  445.     while (!node->parent.isOther() && node->parent->weight < node->weight) {
  446.       Node* parent = node->parent();
  447.       parent->size++;
  448.       if (parent->right == node) {
  449.         rotateLeft(parent);
  450.       } else {
  451.         rotateRight(parent);
  452.       }
  453.     }
  454.     while (!node->parent.isOther()) {
  455.       node = node->parent();
  456.       node->size++;
  457.     }
  458.   }
  459.  
  460.   template<bool isConst>
  461.   void insert(IterImpl<isConst> it, Node* node) {
  462.     if (it.pos.isOther()) {
  463.       push_back_node(node);
  464.       return;
  465.     }
  466.     Node* cur = it.pos();
  467.     if (node->weight <= cur->weight) {
  468.       node->parent = cur;
  469.       node->size = 1;
  470.       node->left = cur->left;
  471.       if (cur->left != nullptr) {
  472.         node->size += cur->left->size;
  473.         cur->left->parent = node;
  474.       }
  475.       cur->left = node;
  476.       cur->size++;
  477.       balanceDown(node);
  478.       while (!cur->parent.isOther()) {
  479.         cur = cur->parent();
  480.         cur->size++;
  481.       }
  482.       return;
  483.     } else {
  484.       node->left = cur->left;
  485.       if (cur->left != nullptr) {
  486.         cur->left->parent = node;
  487.       }
  488.       node->right = cur;
  489.       node->parent = cur->parent;
  490.       cur->parent = node;
  491.       node->size = cur->size + 1;
  492.       cur->left = nullptr;
  493.       cur->size = 1;
  494.       if (cur->right != nullptr) {
  495.         cur->size += cur->right->size;
  496.       }
  497.       if (node->parent.isOther()) {
  498.         root = node;
  499.       } else {
  500.         if (node->parent->right == cur) {
  501.           node->parent->right = node;
  502.         } else {
  503.           node->parent->left = node;
  504.         }
  505.       }
  506.       balanceUp(node);
  507.       return;
  508.     }
  509.   }
  510.  
  511.  public:
  512.   TreapList(uint64_t seed) : rnd(seed) {
  513.   }
  514.   TreapList() : rnd(rnd64()) {
  515.   }
  516.  
  517.   ~TreapList() {
  518.     clear();
  519.   }
  520.  
  521.   using Iterator = IterImpl<false>;
  522.   using ConstIterator = IterImpl<true>;
  523.  
  524.   void clear() {
  525.     if (root != nullptr) {
  526.       freeNodes(root);
  527.     }
  528.     root = nullptr;
  529.   }
  530.  
  531.   Iterator begin() {
  532.     return root ? Iterator(getFirstVertex(root)) : Iterator(this);
  533.   }
  534.  
  535.   ConstIterator begin() const {
  536.     return root ? ConstIterator(getFirstVertex(root)) : ConstIterator(const_cast<TreapList*>(this));
  537.   }
  538.  
  539.   ConstIterator cbegin() const {
  540.     return root ? ConstIterator(getFirstVertex(root)) : ConstIterator(const_cast<TreapList*>(this));
  541.   }
  542.  
  543.   Iterator end() {
  544.     return Iterator(this);
  545.   }
  546.  
  547.   ConstIterator end() const {
  548.     return ConstIterator(const_cast<TreapList*>(this));
  549.   }
  550.  
  551.   ConstIterator cend() const {
  552.     return ConstIterator(const_cast<TreapList*>(this));
  553.   }
  554.  
  555.   uint32_t size() const {
  556.     if (root == nullptr) {
  557.       return 0;
  558.     }
  559.     return root->size;
  560.   }
  561.  
  562.   Iterator get(uint32_t index) {
  563.     return Iterator(this, index);
  564.   }
  565.  
  566.   ConstIterator get(uint32_t index) const {
  567.     return ConstIterator(const_cast<TreapList*>(this), index);
  568.   }
  569.  
  570.   T& operator[](uint32_t index) {
  571.     return *get(index);
  572.   }
  573.  
  574.   const T& operator[](uint32_t index) const {
  575.     return *get(index);
  576.   }
  577.   void push_back(const T& value) {
  578.     push_back_node(createNode(value));
  579.   }
  580.   void push_back(T&& value) {
  581.     push_back_node(createNode(std::move(value)));
  582.   }
  583.   void push_front(const T& value) {
  584.     push_front_node(createNode(value));
  585.   }
  586.   void push_front(T&& value) {
  587.     push_front_node(createNode(std::move(value)));
  588.   }
  589.   void insert(Iterator pos, const T& value) {
  590.     insert(pos, createNode(value));
  591.   }
  592.   void insert(Iterator pos, T&& value) {
  593.     insert(pos, createNode(std::move(value)));
  594.   }
  595.   void insert(ConstIterator pos, const T& value) {
  596.     insert(pos, createNode(value));
  597.   }
  598.   void insert(ConstIterator pos, T&& value) {
  599.     insert(pos, createNode(std::move(value)));
  600.   }
  601.   template<bool isConst>
  602.   void erase(IterImpl<isConst> it) {
  603.     if (it.pos.isOther()) {
  604.       return;
  605.     }
  606.     Node* cur = it.pos();
  607.     while (cur->left != nullptr || cur->right != nullptr) {
  608.       if (cur->left != nullptr && (cur->right == nullptr || cur->left->weight >= cur->right->weight)) {
  609.         rotateRight(cur);
  610.       } else {
  611.         rotateLeft(cur);
  612.       }
  613.     }
  614.     if (cur->parent.isOther()) {
  615.       delete cur;
  616.       root = nullptr;
  617.     } else {
  618.       if (cur->parent->right == cur) {
  619.         cur->parent->right = nullptr;
  620.       } else {
  621.         cur->parent->left = nullptr;
  622.       }
  623.       Node* tmp = cur->parent();
  624.       delete cur;
  625.       cur = tmp;
  626.       cur->size--;
  627.       while (!cur->parent.isOther()) {
  628.         cur->parent->size--;
  629.         cur = cur->parent();
  630.       }
  631.     }
  632.   }
  633.  
  634.   void check(Node* node) {
  635.     uint32_t size = 1;
  636.     if (node->left != nullptr) {
  637.       check(node->left);
  638.       if (node->weight < node->left->weight) {
  639.         std::cerr << "check3" << std::endl;
  640.       }
  641.       if (node->left->parent.isOther() || node->left->parent() != node) {
  642.         std::cerr << "check6" << std::endl;
  643.       }
  644.       size += node->left->size;
  645.     }
  646.     if (node->right != nullptr) {
  647.       check(node->right);
  648.       if (node->weight < node->right->weight) {
  649.         std::cerr << "check4" << std::endl;
  650.       }
  651.       if (node->right->parent.isOther() || node->right->parent() != node) {
  652.         std::cerr << "check7" << std::endl;
  653.       }
  654.       size+= node->right->size;
  655.     }
  656.     if (size != node->size) {
  657.       std::cerr << "check5" << std::endl;
  658.     }
  659.   }
  660.   void check() {
  661.     if (root != nullptr) {
  662.       check(root);
  663.       if (!root->parent.isOther()) {
  664.         std::cerr << "check1" << std::endl;
  665.       }
  666.       if (root->parent.other() != this) {
  667.         std::cerr << "check2" << std::endl;
  668.       }
  669.     }
  670.   }
  671. };
  672.  
  673. struct Generator {
  674.   TreapList<int> tree;
  675.   using It = TreapList<int>::Iterator;
  676.   std::vector<int> result;
  677.   int left, right;
  678.   It itLeft, itRight;
  679.   int e1, e2, e3, e4, e5;
  680.   std::array<It, 5> its;
  681.  
  682.   void downIteration() {
  683.     auto leftCopy = itLeft;
  684.     std::array<int, 4> ts;
  685.     for (int i = 0; i < 4; i++) {
  686.       int& v = *leftCopy;
  687.       ++leftCopy;
  688.       ts[i] = v;
  689.       result[*its[i]] = left + i;
  690.       v = *its[i];
  691.     }
  692.     *its[0] = ts[2];
  693.     *its[1] = ts[0];
  694.     *its[2] = ts[1];
  695.     int last = *itRight;
  696.     *itRight = ts[3];
  697.     *its[3] = last;
  698.     left += 4;
  699.     itLeft = leftCopy;
  700.   }
  701.  
  702.   void upIteration() {
  703.     auto rightCopy = itRight;
  704.     int& v1 = *rightCopy;
  705.     int t1 = v1;
  706.     v1 = *its[4];
  707.     result[v1] = right;
  708.     --rightCopy;
  709.     int& v2 = *rightCopy;
  710.     int t2 = v2;
  711.     v2 = *its[3];
  712.     result[v2] = right - 1;
  713.     --rightCopy;
  714.     int& v3 = *rightCopy;
  715.     int t3 = v3;
  716.     v3 = *its[2];
  717.     result[v3] = right - 2;
  718.     int v4 = *its[1];
  719.     result[v4] = right - 3;
  720.  
  721.     *its[1] = *itLeft;
  722.     *its[3] = t1;
  723.     *its[4] = t2;
  724.     *itLeft = t3;
  725.     tree.erase(its[2]);
  726.     tree.insert(rightCopy, v4);
  727.     --rightCopy;
  728.     --rightCopy;
  729.     right -= 4;
  730.     itRight = rightCopy;
  731.   }
  732.  
  733.   void genEq(std::ostream& out, int n) {
  734.     tree.clear();
  735.     for (int i = 0; i < n; i++) {
  736.       tree.push_back(i);
  737.     }
  738.     result.resize(n);
  739.     std::fill(result.begin(), result.end(), -2);
  740.     for (int i = 0; i < 67; i++) {
  741.       result[2 * i] = -3;
  742.       result[2 * i + 1] = -1;
  743.     }
  744.     left = 0;
  745.     right = n - 1;
  746.     itLeft = tree.begin();
  747.     itRight = tree.end() - 1;
  748.     int value = 0;
  749.     while (right - left >= 47) {
  750.       int len = right - left + 1;
  751.       int s = (len >> 3) + (len >> 6) + 1;
  752.       e3 = (left + right) / 2;
  753.       e2 = e3 - s;
  754.       e1 = e2 - s;
  755.       e4 = e3 + s;
  756.       e5 = e4 + s;
  757.       its = {tree.get(e1), tree.get(e2), tree.get(e3), tree.get(e4), tree.get(e5)};
  758.       for (size_t i = 0; i < 5; i++) {
  759.         int idx = *its[i];
  760.         if (result[idx] == -3) {
  761.           if (result[idx + 1] >= 0 && (idx == 0 || result[idx - 1] >= 0)) {
  762.             result[idx] = -2;
  763.           }
  764.         }
  765.       }
  766.       for (size_t i = 0; i < 5; i++) {
  767.         for (size_t j = i + 1; j < 5; j++) {
  768.           if (result[*its[i]] > result[*its[j]]) {
  769.             std::swap(*its[i], *its[j]);
  770.           }
  771.         }
  772.       }
  773.       if (result[*its[2]] < -2) {
  774.         break;
  775.       }
  776.       result[*its[2]] = value;
  777.       result[*its[3]] = value;
  778.       result[*its[4]] = value;
  779.       value++;
  780.       int v1 = *its[2];
  781.       int v2 = *its[3];
  782.       int v3 = *its[4];
  783.       tree.erase(its[2]);
  784.       tree.erase(its[3]);
  785.       tree.erase(its[4]);
  786.       auto ins = itRight + 1;
  787.       tree.insert(ins, v1);
  788.       tree.insert(ins, v2);
  789.       tree.insert(ins, v3);
  790.       right -= 3;
  791.     }
  792.     for (int marker = -1; marker >= -3; marker--)
  793.     {
  794.       auto it = itLeft;
  795.       for (int i = left; i <= right; i++) {
  796.         if (result[*it] == marker) {
  797.           result[*it] = value;
  798.         }
  799.         ++it;
  800.       }
  801.       value++;
  802.     }
  803.     for (int i = 0; i < n; i++) {
  804.       result[i] = value - result[i];
  805.     }
  806.     out << n;
  807.     out << '\n';
  808.     for (int i = 0; i < n; ++i) {
  809.       if (i) out << " ";
  810.       out << result[i] + 2;
  811.     }
  812.     out << '\n';
  813.   }
  814. };
  815.  
  816. int main() {
  817.   std::cin.sync_with_stdio(false);
  818.   std::cin.tie(nullptr);
  819.   Generator().genEq(std::cout, 100000);
  820.   return 0;
  821. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!