Advertisement
Guest User

Untitled

a guest
Oct 21st, 2018
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. long long isBit (long long num, int bit_number) {
  5. return (1 & (num >> bit_number));
  6. }
  7.  
  8. int Partition (std::vector<long long>& numbers, int left, int right, int bit_number) {
  9. if (right <= left)
  10. return left;
  11. int i = left, j = right;
  12. while (i <= j) {
  13. for(;i <= right && isBit(numbers[i], bit_number) == 0; ++i) {}
  14. for(;j >= left && isBit(numbers[j], bit_number) == 1; --j) {}
  15. if (i < j) {
  16. long long i2 = i;
  17. i = j;
  18. j = i2;
  19. i++;
  20. j--;
  21. }
  22. }
  23. }
  24.  
  25. void BinaryMSD (std::vector <long long>& numbers, int left, int right, int bit_number) {
  26. int q = Partition (numbers, left, right, bit_number);
  27. if (bit_number > 0) {
  28. if (q < right) {
  29. BinaryMSD(numbers, q, right, bit_number - 1);
  30. }
  31. if (q > left) {
  32. BinaryMSD(numbers, left, q - 1, bit_number - 1);
  33. }
  34. }
  35. }
  36.  
  37. int main () {
  38. int n;
  39. std::cin >> n;
  40. std::vector <long long> numbers;
  41. for (int i = 0; i < n; ++i) {
  42. int a;
  43. std::cin >> a;
  44. numbers.push_back(a);
  45. }
  46. BinaryMSD (numbers, 0, numbers.size() - 1, 63);
  47. for (int i = 0; i < n; ++i) {
  48. std::cout << numbers[i] << ' ';
  49. }
  50. return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement