~quf/computers-are-fast-2020

computers-are-fast-2020/src/15.c -rw-r--r-- 1.8 KiB
6f56515eLukas Himbert Draw the rest of the fine owl. 1 year, 7 months ago
                                                                                
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
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <string.h>

#define N1 2020
#define N2 30000000

#if defined(__TINYC__) && defined(__x86_64__)
#define USE_ASM
#endif

#ifdef USE_ASM
#define STR(x) STR_(x)
#define STR_(x) #x
#endif

int main(void) {
  int_least32_t *spoken = calloc(N2, sizeof *spoken);
  if (spoken == NULL) {
    fprintf(stderr, "Allocation error.\n");
    return 1;
  }
  for (size_t i = 0; i < N2; ++i) {
    spoken[i] = INT_LEAST32_MAX;
  }
  int_fast32_t i = 1;
  {
    size_t n;
    while (scanf("%zu%*c", &n) > 0) {
      spoken[n * (n < N2)] = i++;
    }
    if (ferror(stdin) || !feof(stdin)) {
      fprintf(stderr, "Input error.\n");
      return 1;
    }
  }
  int_least32_t n = 0;
  for (; i < N1; ++i) {
    int_least32_t t = spoken[n];
    spoken[n] = (int_least32_t) i;
    n = i - t;
    n = (n >= 0)? n : 0;
  }
  printf("%lu\n", (unsigned long) n);
#ifdef USE_ASM
    __asm__ (
      /* start: save frame pointer & null ecx */
      "mov %%rbp, %%r8\n"
      "xor %%ecx, %%ecx\n"
      "loop:\n"
      /* t = spoken[n]; */
      "mov %%eax, %%rbp\n"
      "lea (%2, %%rbp, 4), %%rax\n"
      "mov (%%rax), %%edx\n"
      /* spoken[n] = i; */
      "mov %%ebx, (%%rax)\n"
      /* n = max(i - t, 0); (branchless) */
      "mov %%ebx, %%eax\n"
      "sub %%edx, %%eax\n"
      "cmovs %%ecx, %0\n"
      /* loop */
      "inc %%rbx\n"
      "cmp $"STR(N2)", %%rbx\n"
      "jne loop\n"
      /* end: restore frame pointer */
      "mov %%r8, %%rbp\n"
    : "+a"(n)
    , "+b"(i)
    : "r"(spoken)
    : "cc", "memory", "ecx", "edx", "r8"
    );
#else
  for (; i < N2; ++i) {
    int_least32_t t = spoken[n];
    spoken[n] = (int_least32_t) i;
    n = i - t;
    n = (n >= 0)? n : 0;
  }
#endif
  printf("%lu\n", (unsigned long) n);
  free(spoken);
  return 0;
}