Solve in go: 0.16s

1 files changed, 99 insertions, 0 deletions

diff --git a/kattis-kth-alginda-quicksort/radix.go b/kattis-kth-alginda-quicksort/radix.go
new file mode 100644
index 0000000..d847547
--- /dev/null
+++ b/kattis-kth-alginda-quicksort/radix.go
@@ -0,0 +1,99 @@
+package main
+
+import (
+	"os"
+)
+
+var xs [600_000]int32
+var ys [600_000]int32
+
+func radixSort(n int) {
+	ys, xs := xs[:n], ys[:n]
+	for m := 0; m < 32; m += 8 {
+		xs, ys = ys, xs
+
+		var counts [256]int32
+		for _, x := range xs {
+			counts[x>>m&0xff]++
+		}
+
+		for i := 1; i < len(counts); i++ {
+			counts[i] += counts[i-1]
+		}
+
+		for i := len(xs) - 1; i >= 0; i-- {
+			counts[xs[i]>>m&0xff]--
+			ys[counts[xs[i]>>m&0xff]] = xs[i]
+		}
+	}
+}
+
+var buf [600_000 * 12]byte
+
+func main() {
+	n, _ := os.Stdin.Read(buf[:])
+	b := buf[:n]
+	i := 0
+
+	count := 0
+	for ; b[i] != ' '; i++ {
+		count = count*10 + int(b[i]-'0')
+	}
+	i++ // skip space
+
+	for j := 0; j < count; j++ {
+		x := int32(0)
+		neg := false
+		if b[i] == '-' {
+			neg = true
+			i++
+		}
+		for ; '0' <= b[i] && b[i] <= '9'; i++ {
+			x = x*10 + int32(b[i]-'0')
+		}
+		i++ // skip space
+
+		if neg {
+			x = -x
+		}
+		var bit int32 = 1
+		xs[j] = x ^ bit<<31
+	}
+
+	radixSort(count)
+
+	b = buf[:]
+	i = 600_000*12 - 1
+	b[i] = '\n'
+	i--
+	for j := count - 1; j >= 0; j-- {
+		var bit int32 = 1
+		sx := xs[j] ^ bit<<31
+		neg := sx < 0
+		var x uint32
+		if neg {
+			x = uint32(-sx)
+		} else {
+			x = uint32(sx)
+		}
+		if x == 0 {
+			b[i] = '0'
+			i--
+		}
+		for x > 0 {
+			b[i] = '0' + byte(x%10)
+			x /= 10
+			i--
+		}
+		if neg {
+			b[i] = '-'
+			i--
+		}
+		if j > 0 {
+			b[i] = '\n'
+			i--
+		}
+	}
+
+	os.Stdout.Write(b[i+1:])
+}