Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdint.h>
  4. #include <iterator>
  5.  
  6. template<class Iterator>
  7. void myPrint(Iterator begin, Iterator end){
  8. for(Iterator it = begin; it != end; ++it){
  9. std::cout << *it << ' ';
  10. }
  11. std::cout << '\n';
  12. }
  13.  
  14. template<class Iterator>
  15. int64_t mergeSortM(Iterator begin, Iterator end){
  16.  
  17. int64_t count = 0;
  18.  
  19. int64_t length = 1;
  20. Iterator left_i, right_i, left_j, right_j;
  21. while(length <= end - begin){
  22.  
  23. //std::cout << length << "\n";
  24.  
  25. int64_t step = 0;
  26. while(true){
  27. if ((step+1) * length < end - begin ){
  28. left_i = begin + step * length;
  29. ++step;
  30. right_i = begin + step * length;
  31. }
  32. else{
  33. break;
  34. }
  35. left_j = begin + step * length;
  36. ++step;
  37. if (step * length <= end - begin ){
  38. right_j = begin + step * length;
  39. }
  40. else{
  41. right_j = end;
  42. }
  43.  
  44. //std::cout << *left_i << ' ' << *left_j << '\n';
  45.  
  46. std::vector<int64_t> temp;//<typename std::iterator_traits<Iterator>::type_value> temp;
  47.  
  48. Iterator start = left_i;
  49.  
  50. while (true){
  51. if (*left_i <= *left_j){
  52. temp.push_back(*left_i);
  53. left_i += 1;
  54. if (left_i == right_i){
  55. for(Iterator it = left_j; it != right_j; ++it){
  56. temp.push_back(*it);
  57. }
  58. break;
  59. }
  60. }
  61. else {
  62.  
  63. count += right_i - left_i;
  64.  
  65. temp.push_back(*left_j);
  66. left_j += 1;
  67. if (left_j == right_j){
  68. for(Iterator it = left_i; it != right_i; ++it){
  69. temp.push_back(*it);
  70. }
  71. break;
  72. }
  73. }
  74. }
  75.  
  76. for(int64_t i = 0; i < temp.size(); ++i){
  77. *start = temp[i];
  78. ++start;
  79. }
  80.  
  81. //myPrint(begin, end);
  82. }
  83. length *= 2;
  84. }
  85.  
  86. return count;
  87. }
  88.  
  89.  
  90.  
  91. int main(){
  92. std::vector<int64_t> line;
  93. int64_t temp;
  94. while (std::cin >> temp){
  95. line.push_back(temp);
  96. }
  97.  
  98. std::cout << mergeSortM(line.begin(), line.end());
  99.  
  100. //myPrint(line.begin(), line.end());
  101.  
  102. return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement