1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
# 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); */
}
=#
|
