# https://kth.kattis.com/problems/kth.alginda.quicksort using OffsetArrays function radixsort(xs::AbstractVector{UInt32}) xs, ys = similar(xs), xs counts = OffsetArray(Vector{UInt32}(undef, 256), 0:255) for m = 0:8:32 xs, ys = ys, xs fill!(counts, 0) for x = xs counts[x >> m & 0xff] += 1 end sum = 0 for i = firstindex(counts):lastindex(counts) sum += counts[i] counts[i] = sum end for i = length(xs):-1:1 fx = xs[i] >> m & 0xff ys[counts[fx]] = xs[i] counts[fx] -= 1 end end ys end function main() @time xs = map(x -> UInt32(1 << 31) ⊻ parse(Int32, x), readline() |> split)[2:end] @time xs = radixsort(xs) @time for x in xs println(Int32(UInt32(1 << 31) ⊻ x)) end end main() @time main() #= 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); char *p = buffer; char *end = &buffer[len]; int n = 0; while (*p != ' ') { n *= 10; n += *p - '0'; p++; } while (*p == ' ' || *p == '\n') p++; // 18 ms for (int i = 0; i < n; i++) { int x = 0; bool neg = false; if (*p == '-') { neg = true; p++; } while (p < end && *p != ' ' && *p != '\n') { x *= 10; x += *p - '0'; p++; } while (p < end && (*p == ' ' || *p == '\n')) p++; if (neg) x = -x; xs[i] = x ^ (1 << 31); } // 10 ms radix_sort(n); // 17 ms p = &buffer[BUFFER_MAX - 1]; char *last = p; *p-- = '\n'; for (int i = n - 1; i >= 0; i--) { int signedx = xs[i] ^ (1 << 31); bool neg = signedx < 0; uint32_t x; if (neg) x = -signedx; else x = signedx; do { *p-- = (x % 10) + '0'; x /= 10; } while (x > 0); if (neg) *p-- = '-'; if (i > 0) *p-- = '\n'; } write(1, p + 1, last - p); /* ssize_t c = 0; */ /* while (c < len) c += write(1, &buffer[c], len - c); */ } =#