Initial commit

1 files changed, 146 insertions, 0 deletions

diff --git a/kattis-kth-alginda-quicksort/radix.c b/kattis-kth-alginda-quicksort/radix.c
new file mode 100644
index 0000000..babc0ec
--- /dev/null
+++ b/kattis-kth-alginda-quicksort/radix.c
@@ -0,0 +1,146 @@
+/* https://kth.kattis.com/problems/kth.alginda.quicksort */
+
+#include <unistd.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdint.h>
+/* #include <immintrin.h> */
+
+// longest int: -2147483648
+#define BUFFER_MAX (12 * 600000)
+char buffer[BUFFER_MAX];
+int xs[600000];
+int tmp[600000];
+
+int *radix_sort(int n) {
+    int *out = xs;
+    int *in = tmp;
+    // we loop an even amount of times so the completely sorted array
+    // will be in xs, not tmp
+    for (int m = 0; m < 32; m += 8) {
+        int *tmp = out;
+        out = in;
+        in = tmp;
+
+        int counts[256] = { 0 };
+        for (int i = 0; i < n; i++)
+            counts[(uint8_t) (in[i] >> m)]++;
+
+        int sum = 0;
+        for (int i = 0; i < 256; i++) {
+            sum += counts[i];
+            counts[i] = sum;
+        }
+        for (int i = n - 1; i >= 0; i--) {
+            uint8_t fx = in[i] >> m;
+            counts[fx]--;
+            out[counts[fx]] = in[i];
+        }
+    }
+}
+
+int main() {
+    /* char *buffer = malloc(BUFFER_MAX); */
+    /* ssize_t len = 0; */
+    /* while (true) { */
+    /*     if (len >= BUFFER_MAX) return 1; */
+    /*     ssize_t r = read(0, &buffer[len], BUFFER_MAX - len); */
+    /*     len += r; */
+    /*     if (r == 0) */
+    /*         break; */
+    /* } */
+    ssize_t len = read(0, buffer, BUFFER_MAX);
+
+    int curr = 0;
+    int n = 0;
+    while (buffer[curr] != ' ' && buffer[curr] != '\n') {
+        n *= 10;
+        n += buffer[curr] - '0';
+        curr++;
+    }
+    while (buffer[curr] == ' ' || buffer[curr] == '\n') curr++;
+
+    for (int i = 0; i < n; i++) {
+        int x = 0;
+        bool neg = false;
+        if (buffer[curr] == '-') {
+            neg = true;
+            curr++;
+        }
+        while (curr < len && buffer[curr] != ' ' && buffer[curr] != '\n') {
+            x *= 10;
+            x += buffer[curr] - '0';
+            curr++;
+        }
+        while (curr < len && (buffer[curr] == ' ' || buffer[curr] == '\n')) curr++;
+
+        if (neg) x = -x;
+        xs[i] = x ^ (1 << 31);
+    }
+
+    radix_sort(n);
+
+    len = 0;
+    for (int i = 0; i < n; i++, len += 12) {
+        long x = xs[i] ^ (1 << 31);
+        bool neg = false;
+        if (x < 0) {
+            neg = true;
+            x = -x;
+        }
+        int j = 11;
+        buffer[len + j--] = '\n';
+        do {
+            buffer[len + j--] = (x % 10) + '0';
+            x /= 10;
+        } while (x > 0);
+        if (neg) buffer[len + j--] = '-';
+        while (j >= 0) buffer[len + j--] = ' ';
+    }
+
+    /*
+    len = 0;
+
+    __m256i highestbit = _mm256_set1_epi32(1 << 32);
+    __m256i zero = _mm256_set1_epi32(0);
+    __m256i lens = _mm256_set_epi32(0 * 12,
+                                    1 * 12,
+                                    2 * 12,
+                                    3 * 12,
+                                    4 * 12,
+                                    5 * 12,
+                                    6 * 12,
+                                    7 * 12);
+    __m256i lenoffset = _mm256_set1_epi(8 * 12);
+
+    for (int i = 0; i < n; i += 8) {
+        // long x = xs[i] ^ (1 << 31);
+        __m256i xx = _mm256_load_si256(&xs[i]);
+        xx = _mm256_xor_si256(xx, highestbit);
+        // bool neg = false;
+        // if (x < 0) {
+        //     neg = true;
+        //     x = -x;
+        // }
+        __m256i negs = _mm256_cmpgt(zero, xx);
+        xx = _mm256_abs_epi64(xx);
+        // todo...
+        int j = 11;
+        buffer[len + j--] = '\n';
+        do {
+            buffer[len + j--] = (x % 10) + '0';
+            x /= 10;
+        } while (x > 0);
+        if (neg) buffer[len + j--] = '-';
+        while (j >= 0) buffer[len + j--] = ' ';
+
+        // len += 8 * 12
+        lens = _mm256_add_epi32(lens, lenoffset);
+    }
+    */
+    /* ssize_t c = 0; */
+    /* while (c < len) c += write(1, &buffer[c], len - c); */
+    write(1, buffer, len);
+}