blob: 93bd111a5d6fe876e0762c14c18c8b93805daaf4 (
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
101
102
103
104
105
106
107
108
|
/* 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];
int xs[600000];
int tmp[600000];
void radix_sort(int n) {
int *out = xs;
int *in = tmp;
// we loop an even amount of times so the final sorted array will be in xs.
// if we looped an odd amount of times this would not be the case
for (int m = 0; m < 32; m += 8) {
int *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() {
/* 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); */
}
|
