uppgb.c (1938B)
1 #include "common.h" 2 3 #define NINDICES 3 4 5 void printv(const uint16_t *v, const size_t n) { 6 size_t i; 7 for (i = 0; i < n; i++) { 8 printf("\t%u", v[i]); 9 } 10 } 11 12 static inline int64_t mod(int64_t a, int64_t b) { 13 int64_t r = a % b; 14 return r < 0 ? r + b : r; 15 } 16 17 void compute_next(uint16_t *nxt, const uint16_t *prev, const int64_t *d, 18 const size_t i, const size_t n) { 19 assert(i < n); 20 21 if (d[i] == 0) { 22 memcpy(nxt, prev, n * sizeof(*prev)); 23 } else { 24 int64_t ti = mod(((int64_t)prev[i]) + d[i], (int64_t)(n - 1)); 25 int64_t tip = ti == 0 ? n - 1 : ti; 26 27 size_t j; 28 for (j = 0; j < n; j++) { 29 if (j == i) { 30 nxt[j] = tip; 31 } else if (tip <= prev[j] && prev[j] < prev[i]) { 32 nxt[j] = prev[j] + 1; 33 } else if (prev[i] < prev[j] && prev[j] <= tip) { 34 assert(prev[j] > 0); 35 nxt[j] = prev[j] - 1; 36 } else { 37 nxt[j] = prev[j]; 38 } 39 } 40 } 41 } 42 43 size_t index_of(const uint16_t value, const uint16_t *v, const size_t n) { 44 size_t i; 45 for (i = 0; i < n; i++) { 46 if (v[i] == value) 47 return i; 48 } 49 return SIZE_MAX; 50 } 51 52 static inline void compute_first(uint16_t *out, const int64_t *d, 53 const size_t n) { 54 size_t i = 0; 55 while (d[i] != 0) { 56 i++; 57 } 58 59 size_t j; 60 for (j = 0; j < n; j++) { 61 out[(i + j) % n] = j; 62 } 63 } 64 65 int main(int argc, char **argv) { 66 char **lines; 67 size_t n = readlines(&lines, "input"); 68 printf("#lines: %lu\n", n); 69 70 int64_t d[n]; 71 parse(d, lines, n); 72 73 size_t i, j; 74 75 for (i = 0; i < n; i++) { 76 d[i] *= 811589153; 77 } 78 79 uint16_t v[2 * n]; 80 compute_first(v, d, n); 81 82 for (i = 0; i < 10 * n; i++) { 83 compute_next(&v[((i + 1) % 2) * n], &v[(i % 2) * n], d, i % n, n); 84 } 85 86 size_t ind[3] = {1000 % n, 2000 % n, 3000 % n}; 87 88 int64_t sum = 0; 89 for (j = 0; j < NINDICES; j++) { 90 sum += d[index_of(ind[j], &v[(i % 2) * n], n)]; 91 } 92 93 printf("%lld\n", sum); 94 }