blob: d8475470988c98f9332c58c89b33a8c058fff89b (
plain) (
blame)
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
|
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:])
}
|
