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
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct rle {
unsigned char count : 2;
unsigned char digit : 2;
};
struct buf {
struct rle *buf;
size_t count;
};
size_t len(const struct buf *buf)
{
size_t len = 0;
for (size_t i = 0; i < buf->count; i++)
len += buf->buf[i].count;
return len;
}
void append(struct buf *buf, unsigned char digit)
{
if (buf->count == 0 || buf->buf[buf->count - 1].digit != digit) {
buf->buf[buf->count++] = (struct rle){ 1, digit };
return;
}
buf->buf[buf->count - 1].count++;
}
void solve(const struct buf *input, size_t *p1, size_t *p2) {
struct buf bufs[2];
bufs[0].buf = malloc(sizeof *bufs[0].buf * 0xa00000);
bufs[1].buf = malloc(sizeof *bufs[1].buf * 0xa00000);
int srcbuf = 0;
memcpy(bufs[srcbuf].buf, input->buf,
sizeof *bufs[srcbuf].buf * input->count);
bufs[srcbuf].count = input->count;
for (int i = 0; i < 50; i++) {
if (i == 40) *p1 = len(&bufs[srcbuf]);
bufs[!srcbuf].count = 0;
for (int j = 0; j < bufs[srcbuf].count; j++) {
append(&bufs[!srcbuf], bufs[srcbuf].buf[j].count);
append(&bufs[!srcbuf], bufs[srcbuf].buf[j].digit);
}
srcbuf = !srcbuf;
}
*p2 = len(&bufs[srcbuf]);
}
int main(void)
{
struct buf input = {
(struct rle []){
{3, 1},
{1, 3},
{3, 2},
{2, 1},
{1, 3},
},
5,
};
size_t p1, p2;
solve(&input, &p1, &p2);
printf("%zu\n%zu\n", p1, p2);
}
|
