Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- using namespace std;
- bool readInt(int &num) {
- int ch = getchar_unlocked();
- num = 0;
- for (; 48 <= ch && ch <= 57; ch = getchar_unlocked()) {
- num = (num << 3) + (num << 1) + ch - 48;
- }
- if (ch == 32)
- return true;
- if (ch == 10)
- return false;
- }
- void printInt(int n) {
- if (n > 0) {
- printInt(n / 10);
- }
- if (n != 0)
- putchar_unlocked(n % 10 + 48);
- }
- const int k = 256;
- int counts[k];
- void CountingSort(int *arr, int* result, int &n, int r) {
- int byte = 255 << r;
- for (int i = 0; i < k; ++i) counts[i] = 0;
- for (int i = 0; i < n; ++i) {
- ++counts[(arr[i] & byte) >> r];
- }
- for (int i = 1; i < k; ++i) {
- counts[i] += counts[i - 1];
- }
- for (int i = n - 1; i >= 0; --i) {
- result[--counts[(arr[i] & byte) >> r]] = arr[i];
- }
- }
- void LSDSort(int *arr, int &n) {
- int* result = new int[n];
- CountingSort(arr, result, n, 0);
- CountingSort(result, arr, n, 8);
- CountingSort(arr, result, n, 16);
- CountingSort(result, arr, n, 24);
- }
- const int maxSize = 25000000;
- int main() {
- int* arr = new int[maxSize];
- int x = 0;
- int size = 0;
- while (readInt(x)) {
- arr[size++] = x;
- }
- arr[size++] = x;
- LSDSort(arr, size);
- for (int i = 9; i < size; i += 10) {
- printInt(arr[i]);
- putchar_unlocked(32);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement