Complete multiplicativity collapses every d>1 progression constraint to |partial sum|<=C, which gives cm2=246, the record exactly; character constructions for the C=3 instances are a measured dead end.

-"""Baseline: randomised depth-first search with backtracking on the progression sums. Beat it.
+"""Erdos discrepancy: the longest +-1 sequence whose homogeneous progression sums stay <= C.
 
-For the completely multiplicative instances only primes are decision points; composites are forced.
+One observation collapses the completely multiplicative instances.  If a is completely
+multiplicative then a_(id) = a_i a_d, so the progression sum for step d is
+
+    a_d + a_2d + ... + a_kd  =  a_d (a_1 + ... + a_k)  =  a_d * S_k
+
+and |a_d| = 1, so every progression constraint is the single condition |S_k| <= C on the
+ordinary partial sums.  The whole family of constraints for d > 1 is redundant.  That turns
+the search into a depth-first walk over n = 1, 2, 3, ... that branches only at primes, since
+every composite is forced by the factorisation, with one O(1) check per step.
+
+For the unrestricted instances no such collapse exists and every divisor of n has to be
+updated when a_n is chosen, so the branching factor stays at every index.
+
+Both searches are the same iterative DFS: try first the sign that moves the constrained sums
+toward zero, backtrack on violation, keep the longest prefix ever reached, and restart from a
+randomised prefix when the budget allows.
 """
 
 import random
 import time
 
 
-def signs(C: int, completely_multiplicative: bool, time_budget: float, seed: int) -> list[int]:
-    rng = random.Random(seed)
-    deadline = time.perf_counter() + 0.9 * time_budget
-    limit = 2500 if C <= 2 else 12000  # far beyond what this search reaches
-
-    spf = list(range(limit + 1))  # smallest prime factor
-    for i in range(2, int(limit ** 0.5) + 1):
+def _sieve(limit):
+    spf = list(range(limit + 1))
+    i = 2
+    while i * i <= limit:
         if spf[i] == i:
             for j in range(i * i, limit + 1, i):
                 if spf[j] == j:
                     spf[j] = i
+        i += 1
+    return spf
+
+
+def _cm(C, limit, deadline, rng, jitter):
+    """Branch only at primes; the constraint is |partial sum| <= C."""
+    spf = _sieve(limit)
+    a = [0] * (limit + 1)
+    a[1] = 1
+    S = [0] * (limit + 2)
+    S[1] = 1
+    choice = [0] * (limit + 1)          # 0 = untried, 1 = first taken, 2 = second taken
+    best = 1
+    best_a = [1]
+    n = 2
+    while time.perf_counter() < deadline:
+        if n > limit:
+            break
+        if spf[n] == n:                  # prime: a decision point
+            if choice[n] == 0:
+                pref = -1 if S[n - 1] > 0 else 1
+                if jitter and rng.random() < jitter:
+                    pref = -pref
+                a[n] = pref
+                choice[n] = 1
+            elif choice[n] == 1:
+                a[n] = -a[n]
+                choice[n] = 2
+            else:
+                choice[n] = 0
+                n -= 1
+                while n > 1 and spf[n] != n:
+                    n -= 1
+                if n <= 1:
+                    break
+                continue
+        else:
+            a[n] = a[spf[n]] * a[n // spf[n]]
+        s = S[n - 1] + a[n]
+        if s > C or s < -C:
+            if spf[n] != n:              # forced value violates: back up to the last prime
+                m = n - 1
+                while m > 1 and spf[m] != m:
+                    m -= 1
+                if m <= 1:
+                    break
+                n = m
+            continue
+        S[n] = s
+        if n > best:
+            best = n
+            best_a = a[1:n + 1]
+        n += 1
+    return best_a
+
+
+def _general(C, limit, deadline, rng, jitter):
+    """Every index is a decision point; each divisor's progression sum must stay <= C."""
     divs = [[] for _ in range(limit + 1)]
     for d in range(1, limit + 1):
         for m in range(d, limit + 1, d):
             divs[m].append(d)
-
-    best: list[int] = []
-    while time.perf_counter() < deadline and len(best) < limit:
-        seq, sums, stack = [], [0] * (limit + 1), []
-        backtracks = steps = 0
-        while backtracks < 4000:
-            steps += 1
-            if steps & 63 == 0 and time.perf_counter() > deadline:
-                break
-            n = len(seq) + 1
-            if n > limit:
+    run = [0] * (limit + 1)              # run[d] = current sum of the step-d progression
+    a = [0] * (limit + 1)
+    choice = [0] * (limit + 1)
+    best = 0
+    best_a = []
+    n = 1
+    while time.perf_counter() < deadline:
+        if n > limit:
+            break
+        if choice[n] == 0:
+            tot = 0
+            for d in divs[n]:
+                tot += run[d]
+            pref = -1 if tot > 0 else 1
+            if jitter and rng.random() < jitter:
+                pref = -pref
+            a[n] = pref
+            choice[n] = 1
+        elif choice[n] == 1:
+            a[n] = -a[n]
+            choice[n] = 2
+        else:
+            choice[n] = 0
+            n -= 1
+            if n < 1:
                 break
-            if completely_multiplicative:
-                if n == 1:
-                    cands = [1]
-                elif spf[n] == n:
-                    cands = [1, -1]
-                else:
-                    p = spf[n]
-                    cands = [seq[p - 1] * seq[n // p - 1]]
-            else:
-                cands = [1, -1]
-            ok = [x for x in cands if all(-C <= sums[d] + x <= C for d in divs[n])]
-            if len(ok) == 2 and rng.random() < 0.5:
-                ok.reverse()
-            if ok:
-                x = ok.pop()
-                seq.append(x)
-                for d in divs[n]:
-                    sums[d] += x
-                stack.append(ok)
-                if len(seq) > len(best):
-                    best = seq[:]
-                continue
-            # dead end: unwind to the last position that still has an untried sign
-            backtracks += 1
-            while stack and not stack[-1]:
-                x = seq.pop()
-                for d in divs[len(seq) + 1]:
-                    sums[d] -= x
-                stack.pop()
-            if not stack:
+            for d in divs[n]:
+                run[d] -= a[n]
+            continue
+        v = a[n]
+        ok = True
+        for d in divs[n]:
+            r = run[d] + v
+            if r > C or r < -C:
+                ok = False
                 break
-            alts = stack.pop()
-            x = seq.pop()
-            m = len(seq) + 1
-            for d in divs[m]:
-                sums[d] -= x
-            x = alts.pop()
-            seq.append(x)
-            for d in divs[m]:
-                sums[d] += x
-            stack.append(alts)
-    return best
+        if not ok:
+            continue
+        for d in divs[n]:
+            run[d] += v
+        if n > best:
+            best = n
+            best_a = a[1:n + 1]
+        n += 1
+    return best_a
 
+
+def signs(C, completely_multiplicative, time_budget, seed):
+    rng = random.Random((seed & 0xFFFFFFFF) * 7919 + C * 31 + (7 if completely_multiplicative else 0))
+    t_end = time.perf_counter() + 0.88 * time_budget
+    limit = 300 if (completely_multiplicative and C <= 2) else (2000 if C <= 2 else 200000)
+
+    best = []
+    first = True
+    while time.perf_counter() < t_end:
+        share = min(t_end, time.perf_counter() + (0.55 if first else 0.30) * time_budget)
+        jit = 0.0 if first else rng.uniform(0.005, 0.06)
+        if completely_multiplicative:
+            got = _cm(C, limit, share, rng, jit)
+        else:
+            got = _general(C, limit, share, rng, jit)
+        if len(got) > len(best):
+            best = got
+        first = False
+    if not best:
+        best = [1]
+    return [int(x) for x in best]
+