Guest User

Untitled

a guest
Oct 27th, 2017
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.23 KB | None | 0 0
  1. #include <cstdio>
  2.  
  3. using namespace std;
  4.  
  5. bool readInt(int &num) {
  6. int ch = getchar_unlocked();
  7. num = 0;
  8.  
  9. for (; 48 <= ch && ch <= 57; ch = getchar_unlocked()) {
  10. num = (num << 3) + (num << 1) + ch - 48;
  11. }
  12.  
  13. if (ch == 32)
  14. return true;
  15.  
  16. if (ch == 10)
  17. return false;
  18. }
  19.  
  20. void printInt(int n) {
  21. if (n > 0) {
  22. printInt(n / 10);
  23. }
  24. if (n != 0)
  25. putchar_unlocked(n % 10 + 48);
  26. }
  27.  
  28. const int k = 256;
  29. int counts[k];
  30.  
  31. void CountingSort(int *arr, int* result, int &n, int r) {
  32. int byte = 255 << r;
  33.  
  34. for (int i = 0; i < k; ++i) counts[i] = 0;
  35.  
  36. for (int i = 0; i < n; ++i) {
  37. ++counts[(arr[i] & byte) >> r];
  38. }
  39.  
  40. for (int i = 1; i < k; ++i) {
  41. counts[i] += counts[i - 1];
  42. }
  43.  
  44. for (int i = n - 1; i >= 0; --i) {
  45. result[--counts[(arr[i] & byte) >> r]] = arr[i];
  46. }
  47. }
  48.  
  49. void LSDSort(int *arr, int &n) {
  50. int* result = new int[n];
  51. CountingSort(arr, result, n, 0);
  52. CountingSort(result, arr, n, 8);
  53. CountingSort(arr, result, n, 16);
  54. CountingSort(result, arr, n, 24);
  55. }
  56.  
  57. const int maxSize = 25000000;
  58.  
  59. int main() {
  60. int* arr = new int[maxSize];
  61.  
  62. int x = 0;
  63. int size = 0;
  64. while (readInt(x)) {
  65. arr[size++] = x;
  66. }
  67. arr[size++] = x;
  68.  
  69. LSDSort(arr, size);
  70.  
  71. for (int i = 9; i < size; i += 10) {
  72. printInt(arr[i]);
  73. putchar_unlocked(32);
  74. }
  75. return 0;
  76. }
Add Comment
Please, Sign In to add comment