blob: 4113a94c0437172138572785be2075f9c6d9b886 (
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
100
|
/* https://kth.kattis.com/problems/kth.alginda.quicksort */
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
// longest int: -2147483648
#define BUFFER_MAX (12 * 600000)
char buffer[BUFFER_MAX];
long xs[600000];
long tmp[600000];
void radix_sort(int n) {
long *out = xs;
long *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 < 44; m += 8) {
long *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() {
ssize_t len = read(0, buffer, BUFFER_MAX);
char *p = buffer;
int n = 0;
while (*p != ' ' && *p != '\n') {
n *= 10;
n += *p - '0';
p++;
}
p = &buffer[len - 1];
for (int i = n - 1; i >= 0; i--) {
while (*p == ' ' || *p == '\n') p--;
long x = 0;
bool c = true;
if (c) x += (long)(*p-- - '0') << 0; if (*p == ' ' || *p == '-') c = false;
if (c) x += (long)(*p-- - '0') << 4; if (*p == ' ' || *p == '-') c = false;
if (c) x += (long)(*p-- - '0') << 8; if (*p == ' ' || *p == '-') c = false;
if (c) x += (long)(*p-- - '0') << 12; if (*p == ' ' || *p == '-') c = false;
if (c) x += (long)(*p-- - '0') << 16; if (*p == ' ' || *p == '-') c = false;
if (c) x += (long)(*p-- - '0') << 20; if (*p == ' ' || *p == '-') c = false;
if (c) x += (long)(*p-- - '0') << 24; if (*p == ' ' || *p == '-') c = false;
if (c) x += (long)(*p-- - '0') << 28; if (*p == ' ' || *p == '-') c = false;
if (c) x += (long)(*p-- - '0') << 32; if (*p == ' ' || *p == '-') c = false;
if (c) x += (long)(*p-- - '0') << 36;
if (*p == '-') p--;
else x |= 1l << 40;
xs[i] = x;
}
radix_sort(n);
p = &buffer[BUFFER_MAX - 1];
char *last = p;
*p-- = '\n';
for (int i = n - 1; i >= 0; i--) {
long x = xs[i];
bool neg = x >> 40 == 0;
x &= ~(1l << 40);
*p-- = (x & 0xf) + '0'; x >>= 4;
if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
if (neg) *p-- = '-';
if (i > 0) *p-- = '\n';
}
write(1, p + 1, last - p);
}
|
