Block-ruler floor plus annealing seeded by stretched Wichmann rulers; only n=500 converts. The lead: those seeds have 158 marks at n=10000 against a record of 174, and the whole problem is repairing them.

-"""Baseline: a three-block ruler (a run of unit gaps, then gaps of a+1, then a run of unit gaps at
-the far end), followed by a pass that drops marks whose distances are all measured twice.
-Scores roughly 0.7 of the records. Beat it."""
+"""Sparse rulers: marks in {0..n} whose differences cover every distance 1..n, as few as possible.
 
+Wichmann's explicit family is the usual construction, but it only realises lengths of the form
+4r^2 + 8r + 3 + s(4r + 3), and for the lengths in this pack the only (r, s) that land exactly
+are the degenerate ones: n = 300 is hit solely by r = 0, which needs 102 marks against a
+counting bound of 30.  So the construction is no help here and the work is a search.
+
+Two pieces:
+
+  * An always-valid fallback, the block ruler {0..a-1} together with {a, 2a, ...} for
+    a = ceil(sqrt(n)), which has about 2 sqrt(n) marks.  Every distance d = qa + r is the
+    difference of the mark (q+1)a and the mark a - r.  This is the floor the search never
+    does worse than.
+  * Annealing on a fixed number of marks.  Endpoints 0 and n are pinned, the rest move, the
+    cost is the number of uncovered distances, and a move re-seats one mark, which touches
+    only the k distances through it.  Start at the counting bound round(sqrt(3n + 9/4)) and
+    climb only when a size proves infeasible, so the first search run is already the right
+    size rather than a descent from the fallback.
+"""
+
 import math
 import random
-from collections import Counter
+import time
 
 
-def sparse_ruler(n: int, time_budget: float, seed: int) -> list[int]:
-    rng = random.Random(seed)
-    best = None
-    centre = max(1, int(math.sqrt(n / 2)))
-    for a in range(max(1, centre - 3), centre + 4):
-        # {0..a} measures every d = k(a+1) - i, i in 0..a, against the multiples of a+1;
-        # {n-a..n} measures the tail n - i.  Together that is every distance 1..n.
-        marks = set(range(a + 1)) | set(range(0, n + 1, a + 1)) | set(range(n - a, n + 1))
-        marks = prune(sorted(marks), n, rng)
-        if best is None or len(marks) < len(best):
-            best = marks
-    return best
+def _block(n):
+    a = int(math.ceil(math.sqrt(n)))
+    marks = set(range(0, a))
+    q = a
+    while q < n:
+        marks.add(q)
+        q += a
+    marks.add(n)
+    marks.add(0)
+    return sorted(marks)
 
 
-def prune(marks: list[int], n: int, rng: random.Random) -> list[int]:
-    """Remove marks in random order while every distance stays measured (count >= 1)."""
-    count = [0] * (n + 1)
-    for i in range(len(marks)):
-        for j in range(i + 1, len(marks)):
-            count[marks[j] - marks[i]] += 1
-    alive = set(marks)
-    order = marks[:]
-    rng.shuffle(order)
-    for m in order:
-        if m in (0, n):
+def _covers(marks, n):
+    seen = bytearray(n + 1)
+    k = len(marks)
+    for i in range(k):
+        mi = marks[i]
+        for j in range(i + 1, k):
+            seen[marks[j] - mi] = 1
+    return all(seen[d] for d in range(1, n + 1))
+
+
+def _try_k(n, k, rng, deadline, seed_marks):
+    if k < 2:
+        return None
+    pos = [0, n]
+    # Keep the seed's structure: thin it evenly rather than sampling it at random, which
+    # discards exactly the arrangement that made it worth seeding from.
+    pool = [x for x in seed_marks if 0 < x < n]
+    if len(pool) > k - 2 and k > 2:
+        step = len(pool) / float(k - 2)
+        pool = [pool[int(i * step)] for i in range(k - 2)]
+    pos.extend(pool[:k - 2])
+    while len(pos) < k:
+        v = rng.randint(1, n - 1)
+        if v not in pos:
+            pos.append(v)
+    pos = sorted(set(pos))
+    while len(pos) < k:
+        v = rng.randint(1, n - 1)
+        if v not in pos:
+            pos.append(v)
+            pos.sort()
+
+    cnt = [0] * (n + 1)
+    for i in range(k):
+        for j in range(i + 1, k):
+            cnt[abs(pos[j] - pos[i])] += 1
+    missing = sum(1 for d in range(1, n + 1) if cnt[d] == 0)
+
+    temp = 1.6
+    since = 0
+    best = missing
+    while missing > 0 and time.perf_counter() < deadline:
+        idx = rng.randrange(k)
+        if pos[idx] == 0 or pos[idx] == n:
             continue
-        # distances that pairs through m measure; m+d and m-d may both be alive, so count them
-        mine = Counter(abs(m - o) for o in alive if o != m)
-        if all(count[d] > c for d, c in mine.items()):
-            alive.remove(m)
-            for d, c in mine.items():
-                count[d] -= c
-    return sorted(alive)
+        old = pos[idx]
+        new = rng.randint(1, n - 1)
+        if new in pos:
+            continue
+        delta = 0
+        for j in range(k):
+            if j == idx:
+                continue
+            d = abs(pos[j] - old)
+            cnt[d] -= 1
+            if cnt[d] == 0:
+                delta += 1
+        for j in range(k):
+            if j == idx:
+                continue
+            d = abs(pos[j] - new)
+            if cnt[d] == 0:
+                delta -= 1
+            cnt[d] += 1
+        if delta <= 0 or rng.random() < math.exp(-delta / temp):
+            pos[idx] = new
+            missing += delta
+            if missing < best:
+                best = missing
+                since = 0
+        else:
+            for j in range(k):
+                if j == idx:
+                    continue
+                cnt[abs(pos[j] - new)] -= 1
+                cnt[abs(pos[j] - old)] += 1
+        since += 1
+        if since > 2500:
+            since = 0
+            temp = temp * 0.9 if temp > 0.15 else 1.6
+    return sorted(pos) if missing == 0 else None
 
+
+def _wichmann_seeds(n, limit=24):
+    """Wichmann rulers stretched or squeezed to length exactly n.
+
+    The family realises n = 4r^2 + 8r + 3 + s(4r+3) with 4r+s+3 marks, which almost never
+    lands on a requested length.  But the gap multiset is what matters, so take the (r, s)
+    whose natural length is nearest, then add or remove the shortfall from the long gaps.
+    Coverage is damaged by that adjustment, which is exactly what the annealing then repairs;
+    it is a far better starting point than random marks at the same mark count.
+    """
+    out = []
+    for r in range(0, int(math.sqrt(n)) + 2):
+        base = 4 * r * r + 8 * r + 3
+        step = 4 * r + 3
+        if step <= 0:
+            continue
+        for s in range(0, 2 + (n // step)):
+            nat = base + s * step
+            if abs(nat - n) > max(64, n // 6):
+                continue
+            gaps = ([1] * r + [r + 1] + [2 * r + 1] * r + [4 * r + 3] * s
+                    + [2 * r + 2] * (r + 1) + [1] * r)
+            if not gaps:
+                continue
+            diff = n - sum(gaps)
+            order = sorted(range(len(gaps)), key=lambda i: -gaps[i])
+            i = 0
+            while diff != 0 and i < len(order) * 40:
+                g = order[i % len(order)]
+                if diff > 0:
+                    gaps[g] += 1
+                    diff -= 1
+                elif gaps[g] > 1:
+                    gaps[g] -= 1
+                    diff += 1
+                i += 1
+            if sum(gaps) != n:
+                continue
+            marks = [0]
+            for g in gaps:
+                marks.append(marks[-1] + g)
+            out.append(sorted(set(marks)))
+    # Collect every candidate before ranking.  Returning the first `limit` found walks r
+    # upward from 0 and yields only the degenerate r = 0 rulers, which have ~n/3 marks.
+    out.sort(key=len)
+    return out[:limit]
+
+
+def sparse_ruler(n, time_budget, seed):
+    t0 = time.perf_counter()
+    deadline = t0 + 0.9 * time_budget
+    rng = random.Random((seed & 0xFFFFFFFF) * 1000003 + n)
+
+    best = _block(n)
+    seeds = _wichmann_seeds(n)
+    for m in seeds:                              # a stretched Wichmann may already be valid
+        if len(m) < len(best) and _covers(m, n):
+            best = m
+    seeds.sort(key=len)
+    lo = int(round(math.sqrt(3.0 * n + 2.25)))
+    for k in range(max(2, lo), len(best)):
+        if time.perf_counter() >= deadline:
+            break
+        left = deadline - time.perf_counter()
+        share = left / max(1.0, (len(best) - k) * 0.4)
+        # seed from the Wichmann ruler nearest this mark count, not from random positions
+        src = best
+        for m in seeds:
+            if len(m) >= k:
+                src = m
+                break
+        got = _try_k(n, k, rng, min(deadline, time.perf_counter() + max(0.3, share)), src)
+        if got is not None and len(got) < len(best) and _covers(got, n):
+            best = got
+            break
+    return best
+