docker_space/frontier_cs_7/verify.py

import sys, subprocess

def verify(solution_file, L, R):
    result = subprocess.run(
        ['./tmp_verify'],
        input=f"{L} {R}",
        capture_output=True, text=True, timeout=10
    )
    lines = result.stdout.strip().split('\n')
    n = int(lines[0])
    
    adj = {}  # node -> list of (to, weight)
    indeg = [0] * (n+1)
    outdeg = [0] * (n+1)
    
    for i in range(1, n+1):
        parts = list(map(int, lines[i].split()))
        k = parts[0]
        edges = []
        for j in range(k):
            to, w = parts[1+2*j], parts[2+2*j]
            edges.append((to, w))
            indeg[to] += 1
        outdeg[i] = k
        adj[i] = edges
    
    # Find start (indeg 0) and end (outdeg 0)
    starts = [i for i in range(1, n+1) if indeg[i] == 0]
    ends = [i for i in range(1, n+1) if outdeg[i] == 0]
    
    if len(starts) != 1 or len(ends) != 1:
        return n, False, f"starts={starts}, ends={ends}"
    
    start = starts[0]
    
    # Check no leading zeros
    for to, w in adj[start]:
        if w == 0:
            return n, False, "leading zero"
    
    # DFS to find all path values
    values = set()
    count = [0]
    
    def dfs(node, val):
        count[0] += 1
        if count[0] > 2000000:
            return
        if outdeg[node] == 0:
            values.add(val)
            return
        for to, w in adj[node]:
            dfs(to, val * 2 + w)
    
    dfs(start, 0)
    
    if count[0] > 2000000:
        return n, False, "too many paths"
    
    expected = set(range(L, R+1))
    if values == expected:
        return n, True, "OK"
    else:
        extra = values - expected
        missing = expected - values
        return n, False, f"extra={len(extra)} missing={len(missing)}"

if __name__ == "__main__":
    sol = sys.argv[1]
    L, R = 577837, 979141
    
    import os
    os.system(f"g++ -O2 -o tmp_verify {sol}")
    n, ok, msg = verify(sol, L, R)
    print(f"n={n}, valid={ok}, {msg}")